#include <bits/stdc++.h>
using namespace std;
char nl = '\n';
char sp = ' ';
using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using si = unordered_set<int>;
using sl = unordered_set<ll>;
using tsi = set<int>;
using tsl = set<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using tmii = map<int, int>;
using tmll = map<ll, ll>;
using mii = unordered_map<int, int>;
using mll = unordered_map<ll, ll>;
using pqi = priority_queue<int>;
using pqig = priority_queue<int, vi, greater<int>>;
using pql = priority_queue<ll>;
using pqlg = priority_queue<ll, vl, greater<ll>>;
using pqpii = priority_queue<pii>;
using pqpll = priority_queue<pll>;
#define tp3(T) tuple<T,T,T
#define tp4(T) tuple<T,T,T,T>;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define outrange(x,min,max) ((x)<(min) || (x)>(max))
#define nano (chrono::system_clock::now().time_since_epoch().count())
#define second_since_start ((nano-start)/1e9)
#define init_rng mt19937 rng(nano)
#define randint(a,b) ((a)+rng()%((b)-(a)+1))
void yesno(bool a) {
cout << (a ? "YES\n" : "NO\n");
}
template<typename L, typename R>
ostream& operator<<(ostream& out, const pair<L, R>& p) {
out << '(' << p.first << ',' << p.second << ')';
return out;
}
template<typename T>
ostream& operator<<(ostream& out, vector<T>& v) {
for (auto &i : v) out << i << ' ';
out << nl;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, set<T>& v) {
for (auto &i : v) out << i << ' ';
out << nl;
return out;
}
template<typename T>
ostream& operator<<(ostream& out, unordered_set<T>& v) {
for (auto &i : v) out << i << ' ';
out << nl;
return out;
}
template<typename K, typename V>
ostream& operator<<(ostream& out, map<K, V>& m) {
out << '[';
for (auto &[k, v] : m) {
out << k << ':' << v << sp;
}
out << "]\n";
return out;
}
template<typename K, typename V>
ostream& operator<<(ostream& out, unordered_map<K, V>& m) {
out << '[';
for (auto &[k, v] : m) {
out << k << ':' << v << sp;
}
out << "]\n";
return out;
}
namespace NTT{
ll mod=998244353;
ll w[]= {1, 998244352, 911660635,
372528824, 929031873, 452798380, 922799308, 781712469,
476477967, 166035806, 258648936, 584193783, 63912897,
350007156, 666702199, 968855178, 629671588, 24514907,
996173970, 363395222, 565042129, 733596141, 267099868,
15311432};
ll pow2Inv[]={1, 499122177, 748683265,
873463809, 935854081, 967049217, 982646785, 990445569,
994344961, 996294657, 997269505, 997756929, 998000641,
998122497, 998183425, 998213889, 998229121, 998236737,
998240545, 998242449, 998243401, 998243877, 998244115,
998244234};
int prev_n=-1;
int* rev_bit;
ll __b[1<<21];
void but(ll &_a,ll &_b, ll _w){
ll mul=_w*_b%mod;
_b=_a+mod-mul;
if(_b>=mod) _b-=mod;
_a+=mul;
if(_a>=mod) _a-=mod;
// cout<<_a<<":"<<_b<<":"<<_w<<endl;
}
void intt(ll *a,int n){
int pow2=1<<n;
if(n!=prev_n){
rev_bit=new int[pow2];
for(int i=0;i<pow2;i++){
int rev=0;
int j=i;
for(int k=0;k<n;k++){
rev<<=1;
rev|=(j&1);
j>>=1;
}
rev_bit[i]=rev;
}
}
for(int i=0;i<pow2;i++) __b[i]=a[rev_bit[i]];
for(int L=n;L>0;L--){
// for(int i=0;i<8;i++) cout<<b[i]<<' '<<endl;
int d=1<<(n-L);
int d2=2*d;
ll w1=1;
int w0=w[n-L+1];
for(int i=0;i<d;i++){
for(int j=i;j<pow2;j+=d2){
// cout<<j<<":"<<j+d<<":"<<w1<<endl;
but(__b[j],__b[j+d],w1);
}
w1=(w1*w0%mod);
}
}
ll lenInv=pow2Inv[n];
a[0]=(__b[0]*lenInv)%mod;
for(int i=1;i<pow2;i++) a[i]=(__b[pow2-i]*lenInv)%mod;
prev_n=n;
}
void ntt(ll *a,int n){
int pow2=1<<n;
if(n!=prev_n){
rev_bit=new int[pow2];
for(int i=0;i<pow2;i++){
int rev=0;
int j=i;
for(int k=0;k<n;k++){
rev<<=1;
rev|=(j&1);
j>>=1;
}
rev_bit[i]=rev;
}
}
for(int i=0;i<pow2;i++) __b[i]=a[rev_bit[i]];
for(int L=n;L>0;L--){
int d=1<<(n-L);
int d2=2*d;
ll w1=1;
int w0=w[n-L+1];
for(int i=0;i<d;i++){
for(int j=i;j<pow2;j+=d2){
but(__b[j],__b[j+d],w1);
}
w1=(w1*w0%mod);
}
}
for(int i=0;i<pow2;i++) a[i]=__b[i];
prev_n=n;
}
ll* convolution(ll *a,ll *b,int n) {
int len=1<<n;
ll *c=new ll[len];
ntt(a,n);
ntt(b,n);
for(int i=0;i<len;i++) {
c[i]=(a[i]*b[i])%mod;
}
intt(c,n);
return c;
}
ll *selfConvolution(ll *a,int n) {
int len=1<<n;
ntt(a,n);
for(int i=0;i<len;i++) {
a[i]=(a[i]*a[i])%mod;
}
intt(a,n);
return a;
}
}
using namespace NTT;
ll *factorial;//[upperBound];
ll *factorial_inv;
ll modInv(ll n) {
ll pow=mod-2;
ll result=1;
while(pow>0) {
if((pow&1)==1) result=(result*n)%mod;
n=(n*n)%mod;
pow>>=1;
}
return result;
}
ll modPow(ll n,ll pow) {
ll result=1;
while(pow>0) {
if((pow&1)==1) result=(result*n)%mod;
n=(n*n)%mod;
pow>>=1;
}
return result;
}
void prepareFactorialAndInv(int max) {
factorial=new ll[max+1];
factorial_inv=new ll[max+1];
factorial[0]=1;
for(int i=1;i<=max;i++) {
factorial[i]=factorial[i-1]*i%mod;
}
factorial_inv[max]=modInv(factorial[max]);
for(int i=max-1;i>=0;i--) {
factorial_inv[i]=factorial_inv[i+1]*(i+1)%mod;
}
}
const int MAX=(1<<20)+5;
ll dp[MAX];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
if(n==1){
cout<<"0\n2";
return 0;
}
prepareFactorialAndInv(1<<n);
dp[0]=0;
dp[1]=0;
dp[2]=0;
dp[3]=1;
dp[4]=2;
ll dp_sum=3;
for(int m=3;m<=n;m++){
ll* f=new ll[1<<m];
ll* g=new ll[1<<m];
ll pow2=1<<(m-1);
for(ll j=0;j<pow2;j++){
f[j]=factorial_inv[j]*factorial_inv[pow2-(j+1)]%mod;
g[j]=f[j]*dp[j+1]%mod;
}
for(ll j=pow2;j<2*pow2;j++){
f[j]=0;
g[j]=0;
}
ll* conv=convolution(f,g,m);
ll dp_sum_next=0;
for(ll k=0;k<=m;k++) dp[k]=0;
for(ll k=m+1;k<=(1<<m);k++){
dp[k]=dp_sum*factorial[k-2]%mod*factorial[(1<<m)-k]%mod*conv[k-2]%mod;
dp_sum_next+=dp[k];
if(dp_sum_next>=mod) dp_sum_next-=mod;
}
dp_sum=dp_sum_next;
// cout<<m<<":"<<dp_sum<<nl;
}
ll pow2=modPow(2,(1<<n)-1);
// cout<<pow2<<nl;
for(int k=1;k<=n;k++) cout<<"0\n";
for(int k=n+1;k<=(1<<n);k++){
cout<<pow2*dp[k]%mod<<nl;
}
}
Note that the problem can be solved without FFT.
Let's calculate the probability the leaf on the left is the wooden spoon (then, multiply by $$$2^n$$$).
Let the "$$$i$$$-th" block be the right subtree of the $$$(n-i+1)$$$-th node in the leftmost path (so, blocks contain nodes in positions $$$[1, 1], [2, 2], [3, 4], [5, 8], \dots$$$ from the left). The condition is "each block contains a prefix minimum" (here, a prefix also includes the blocks $$$[1, i-1]$$$).
Let
dp[i][j]
be the number of ways to put all the elements $$$[1, j-1]$$$ in blocks $$$> i$$$ (you will put $$$j$$$ in block $$$i$$$ later, and it will be the minimum of block $$$i$$$, and also a prefix minimum). The condition is now "for decreasing $$$i$$$, $$$j$$$ is strictly increasing". So, you must calculatedp[i][j]
using transitions fromdp[i + 1][k]
with $$$k < j$$$.Note that in the transitions formula there is no factor that depends both on $$$j$$$ and $$$k$$$. So, you can optimize the dp by calculating prefix sums of
dp[i + 1][k]
$$$\cdot \text{ } (\text{product of factors that depend on } k \text{ in the transition})$$$.AC code: 192338327
I don't think all elements [1,j-1] can be put in blocks > i since element 1 only belongs to the block 1? Terribly sorry for the trouble, but do I misunderstand something?
Good point. Don't arrange the tournament like in the solution above (i.e., don't let the left player win), and calculate the probability that the wooden spoon is the node on the left.