网站建设费属于宣传费吗,shopee怎么注册开店,仅对wordpress自带主题有效,wordpress 如何回到初始化CF1784D Wooden Spoon
题目大意
有2n2^n2n个人#xff0c;进行nnn轮比赛。比赛的图是一棵完全二叉树。编号小的人一定能赢编号大的人#xff0c;如果一个人满足#xff1a;
第一次比赛被打败打败这个人的人在第二次比赛中被打败打败上一个人的人在第三次比赛中被打败…\d…CF1784D Wooden Spoon
题目大意
有2n2^n2n个人进行nnn轮比赛。比赛的图是一棵完全二叉树。编号小的人一定能赢编号大的人如果一个人满足
第一次比赛被打败打败这个人的人在第二次比赛中被打败打败上一个人的人在第三次比赛中被打败…\dots…打败上一个人的人在最后一次比赛中被打败
那么这个人就能得到安慰奖。
求对于每个人有多少种编号的排列来比赛叶子的排列使得他能得安慰奖。输出答案模998244353998244353998244353。 题解
我们按照题意来构建这棵二叉树叶子节点就是这个序列而非叶子节点的权值就是其子树中权值最大的点的权值。假如编号为kkk的点能拿安慰奖那么这个点到根的路径上的点的权值一定是单调递减的。
假设这个点到根的权值组成的序列为a0,a1…,ana_0,a_1\dots,a_na0,a1…,an我们依次来看每个点的贡献。
aia_iai的贡献为C(2n−ai−2i−1,2i−1−1)×(2i−1)!C(2^n-a_i-2^{i-1},2^{i-1}-1)\times (2^{i-1})!C(2n−ai−2i−1,2i−1−1)×(2i−1)!。也就是说这个点在没有kkk的那棵子树中还要放小于他的2i−1−12^{i-1}-12i−1−1个点。因为要小于aia_iai而且自己是一定要选的所以要减aia_iai。又因为有kkk的那一边的点不能选所以要减2i−12^{i-1}2i−1。这棵子树内的点的顺序可以任意排列所以要乘上(2i−1)!(2^{i-1})!(2i−1)!。
设fi,sf_{i,s}fi,s表示第iii个数为sss时第iii个数到第nnn个数的贡献gi,sg_{i,s}gi,s表示第iii个数小于等于sss时第iii个数到第nnn个数的贡献和。那么转移式为
fi,sgi1,s−1×C(2n−s−2i−1,2i−1−1)×(2i−1)!f_{i,s}g_{i1,s-1}\times C(2^n-s-2^{i-1},2^{i-1}-1)\times (2^{i-1})!fi,sgi1,s−1×C(2n−s−2i−1,2i−1−1)×(2i−1)!
gi,sgi,s−1fi,sg_{i,s}g_{i,s-1}f_{i,s}gi,sgi,s−1fi,s
因为kkk的位置任意所以最后还要乘上2n2^n2n。那么编号为kkk的点的答案就是g1,k−1×2ng_{1,k-1}\times 2^ng1,k−1×2n。
时间复杂度为O(n×2n)O(n\times 2^n)O(n×2n)。
code
#includebits/stdc.h
using namespace std;
const int N120;
int n;
long long jc[N5],ny[N5];
long long f[25][N5],g[25][N5];
long long mod998244353;
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void init(){jc[0]1;for(int i1;iN;i) jc[i]jc[i-1]*i%mod;ny[N]mi(jc[N],mod-2);for(int iN-1;i0;i--) ny[i]ny[i1]*(i1)%mod;
}
long long C(int x,int y){if(xy) return 0;return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
int main()
{init();scanf(%d,n);for(int s1;s(1n);s){f[n][s]C((1n)-s-(1n-1),(1n-1)-1)*jc[1n-1]%mod;g[n][s](g[n][s-1]f[n][s])%mod;}for(int in-1;i1;i--){for(int s1;s(1n);s){f[i][s]g[i1][s-1]*C((1n)-s-(1i-1),(1i-1)-1)%mod*jc[1i-1]%mod;g[i][s](g[i][s-1]f[i][s])%mod;}}for(int s1;s(1n);s){printf(%lld\n,g[1][s-1]*(1n)%mod);}return 0;
}
