【题解】wannafly挑战赛11
(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）
T1 白兔的分身术
显然取p=n,k=1最优
T1 白兔的分身术
显然取p=n,k=1最优
T2 白兔的式子
可以发现f[n][m]=a^{n-m}b^{m-1}C(n-1,m-1)。
T3 白兔的棋盘
状压DP，f[i][j][s]表示从（1,1）DP到了(i,j)，轮廓线上每个格子是否是空格的状态为s的方案数。放一个xy的矩形时直接转移到f[i][j+y]。
T4 白兔的字符串
枚举T的所有表示法存入哈希表
然后每个S直接查询
长度有10^6级别，所以哈希的姿势要足够优秀，必然很容易冲突
标算是ex_kmp。用R[i]表示S[i..len]和T的最长公共前缀，L[i]表示S[1..i]和T的最长公共后缀，当L[i]+R[i+1]>=|T|时，可以给一段区间打上标记。如果T的一个表示法在某个位置出现则至少会被一个标记覆盖。然后就变成了区间加法，求有多少个正数。用差分+前缀和即可。
T5 白兔的刁难
题目要求的实际上就是，对于任意t，把展开后，x的指数模k为t的所有项的系数之和。那么我们可以利用，带入。那么x的指数模相同的项就会自动合并。
把进行长度为k的DFT，然后每个数求n次幂，再IDFT回来就是答案。
复杂度klogmin(n,998244352)+klogk。既然是求n次幂，那么n可以直接对998244352取模，那个10^{10^6}是吓唬人的。
T6 白兔的游戏
先来求获胜概率，可以发现，如果每堆石子都只有1个，那么获胜概率不是0就是1；否则，获胜概率就是1/2。
如果先手获胜，那么说明游戏是奇数回合结束的，就是说只需要关心结束时的回合数。
一个大小为m的堆，i次操作完的方案数是C(m-1,i-1)。
直接dp，f[i][j]表示前i堆j次操作完的方案数，f[i][j]+=f[i-1][j-k]C(a[i]-1,k-1)*C(j,k) (1<=k<=a[i])。
分治NTT优化。
其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
