CF1784D Wooden Spoon

CF1784D Wooden Spoon

题目大意

有$2^n$个人，进行$n$轮比赛。比赛的图是一棵完全二叉树。编号小的人一定能赢编号大的人，如果一个人满足：

• 第一次比赛被打败
• 打败这个人的人在第二次比赛中被打败
• 打败上一个人的人在第三次比赛中被打败
• $\dots$
• 打败上一个人的人在最后一次比赛中被打败

那么这个人就能得到安慰奖。

求对于每个人，有多少种编号的排列来比赛（叶子的排列），使得他能得安慰奖。输出答案模$998244353$。

题解

我们按照题意来构建这棵二叉树，叶子节点就是这个序列，而非叶子节点的权值就是其子树中权值最大的点的权值。假如编号为$k$的点能拿安慰奖，那么这个点到根的路径上的点的权值一定是单调递减的。

假设这个点到根的权值组成的序列为$a_0,a_1\dots ,a_n$，我们依次来看每个点的贡献。

$a_i$的贡献为$C(2^n-a_i-2^{i-1},2^{i-1}-1)\times (2^{i-1})!$。也就是说，这个点在没有$k$的那棵子树中还要放小于他的$2^{i-1}-1$个点。因为要小于$a_i$，而且自己是一定要选的，所以要减$a_i$。又因为有$k$的那一边的点不能选，所以要减$2^{i-1}$。这棵子树内的点的顺序可以任意排列，所以要乘上$(2^{i-1})!$。

设$f_{i,s}$表示第$i$个数为$s$时第$i$个数到第$n$个数的贡献，$g_{i,s}$表示第$i$个数小于等于$s$时第$i$个数到第$n$个数的贡献和。那么转移式为

$f_{i,s}=g_{i+1,s-1}\times C(2^n-s-2^{i-1},2^{i-1}-1)\times (2^{i-1})!$

$g_{i,s}=g_{i,s-1}+f_{i,s}$

因为$k$的位置任意，所以最后还要乘上$2^n$。那么编号为$k$的点的答案就是$g_{1,k-1}\times 2^n$。

时间复杂度为$O(n\times 2^n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
int n;
long long jc[N+5],ny[N+5];
long long f[25][N+5],g[25][N+5];
long long mod=998244353;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void init(){jc[0]=1;for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;ny[N]=mi(jc[N],mod-2);for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
long long C(int x,int y){if(x<y) return 0;return jc[x]*ny[y]%mod*ny[x-y]%mod; 
}
int main()
{init();scanf("%d",&n);for(int s=1;s<=(1<<n);s++){f[n][s]=C((1<<n)-s-(1<<n-1),(1<<n-1)-1)*jc[1<<n-1]%mod;g[n][s]=(g[n][s-1]+f[n][s])%mod;}for(int i=n-1;i>=1;i--){for(int s=1;s<=(1<<n);s++){f[i][s]=g[i+1][s-1]*C((1<<n)-s-(1<<i-1),(1<<i-1)-1)%mod*jc[1<<i-1]%mod;g[i][s]=(g[i][s-1]+f[i][s])%mod;}}for(int s=1;s<=(1<<n);s++){printf("%lld\n",g[1][s-1]*(1<<n)%mod);}return 0;
}