自闭集训 Day5
生成函数
一般生成函数
无脑地把序列变成多项式：
\[
\{a_i\}\rightarrow A(x)=\sum_{n} a_nx^n
\]
形式幂级数
生成函数是一种形式幂级数。我们不关心这个函数的具体的取值，只关心多项式的系数。在需要的时候可以把\(x\)当成任意值。
例题
求\(\{n^2\}\)的生成函数。
这个……只要知道\(\{{n+k-1\choose k-1}\}\)的生成函数是\(\frac 1 {(1+x)^k}\)就没了。
例题
简单生成函数题，不讲了。
指数型生成函数
指数型生成函数用于搞关于排列组合的题目。
\(\{a_n\}\rightarrow \sum_n a_n\frac{x^n}{n!}\)
原理？有\(k\)种东西，每个有\(a_{1..k}\)个，那么排列的个数就是\(\frac{n!}{\prod a_i!}\)。
只保留偶数项的生成函数：\(\frac{e^x+e^{-x}}{2}\)；只保留奇数项的：\(\frac{e^x-e^{-x}}{2}\)。
循环卷积
循环卷积，即乘出来的多项式的次数对\(n\)取模。
众所周知，FFT是循环卷积。只不过做FFT的时候搞了个足够大的\(n\)使得不会溢出。
二维循环卷积：设矩阵为\(n\times m\)的，那么
\[
DFT(A)_{i,j}=\sum_{k=0}^{n-1}\sum_{l=0}^{m-1} A_{k,l} \omega_n^{ik}\omega_m^{jl}
\]
所以满足
\[
DFT(A*B)=DFT(A)*DFT(B)
\]
（废话，点值当然可以相乘）
求法：先把每一行DFT，再把每一列DFT。
FWT
FWT就是\(k\)维的循环卷积（异或）。
考虑模2的时候，\(\omega=-1\)，然后把点值带进去，发现刚好就是FWT的式子。然后IDFT的时候也是一样的。
于是得到结论：FWT不一定只能做模2的循环卷积，可以做更多其他东西。
（我怎么今天才明白这个道理……早点明白今年省选就能签到成功了……）
任意长度的循环卷积
（以下\(\omega\)均指\(\omega_n\)）
\[
\begin{align*}
B_i&=\sum_{j=0}^{n-1} \omega^{ij}A_j\\
&=\sum_{j=0}^{n-1} \omega^{\frac{i^2+j^2 -(i-j)^2}2}A_j\\
&=\omega^{i^2/2}\sum_{j=0}^{n-1} (A_j\omega^{j^2/2})\omega^{-(i-j)^2/2}
\end{align*}
\]
发现这东西挺像卷积的，但是上界不太对。
\[
C_i=\sum_{j=0}^{i} (A_j\omega^{j^2/2})\omega^{-(i-j-n)^2/2}
\]
然后发现\(B_i\omega^{-i^2/2}=C_{i+n}\)，就没了。
注意这里如果要取模，那么循环卷积能做的条件是\(\omega_n\)在模意义下存在。
由于\(\omega\)有着神奇的性质，所以把\(\omega^{-1}\)带进去求一遍点值再除以n就得到了系数。
某题
毕克讲过，但忘了。
定义一个\(n\times (n-1)\)的矩阵为类型mat，\(mat_{i,j}\)表示二元组为\((i,j)\)的方案数。mat的乘法定义为二维循环卷积。
转移矩阵内的元素显然由mat组成，那么直接乘起来的复杂度是\(n^4\)的，用FFT把点值求出来再乘就优化成了\(n^2\)。
为什么能FFT优化？因为模数很棒，所以存在需要的单位根。
某 TC Hard
有一个\(n\)次多项式\(P(x)\)，满足\([x^i]P(x)=[x^{n-i}]P(x)\)，已知\(P(x)^2\)在模\(x^{n+1}\)意义下的循环卷积，求\(P(x)\)。
可以先把\(P(x)^2\)DFT一下，得到点值。然而在复数域上开根会有俩，比较麻烦。
然后暴力的做法就是直接枚举是哪个，然后判断，显然过不了。
注意我们还有一个性质，于是可以证明\(\omega^i\)的点值和\(\omega^{n-i}\)的点值是一样的。
于是可以枚举前\(n/2\)个，然后判断。
某题
首先把题目改一改，换成恰好走\(n\)次，每次可以选择走或者停，于是答案不变。
然后还是考虑矩阵快速幂，但这次存的是一个数组。数组相乘仍然是循环卷积。
然后这题没了。
牛顿迭代
已知\(G(x)\)，求\(F(x)\)，使得\(G(F(x))=0\)。
考虑倍增，设\(G(F_t(x))=0\pmod{x^{2^t}}\)，求\(F_{t+1}(x)\)。
把\(G\)在\(F_t(x)\)处展开，得到
\[
\begin{align*}
G(F_{t+1}(x))=&G(F_t(x))+
\\&(F_{t+1}(x)-F_t(x))G'(F_t(x))+\\
&(F_{t+1}(x)-F_t(x))^2G''(F_t(x))/2+\\
&\cdots
\end{align*}
\]
注意要模\(x^{2^{t+1}}\)，所以
\[
0=G(F_t(x))+(F_{t+1}(x)-F_t(x))G'(F_t(x))
\]
所以
\[
F_{t+1}(x)=F_t(x)-\frac{G(F_t(x))}{G'(F_t(x))}
\]
多项式除法
把系数reverse一下，然后神奇地发现变成了求逆，就做完了。
多项式多点求值
令\(A_0(x)=\prod\limits_{i=1}^m (x-x_i),A_1(x)=\prod\limits_{i=m+1}^n (x-x_i)\)，那么左边的可以对\(A_0(x)\)取模，右边的对\(A_1(x)\)取模，然后变成子问题处理。
复杂度\(T(n)=2T(n/2)+O(n\log n)=O(n\log^2 n)\)。
多项式多点插值
\[
F(x)=\sum_{i=0}^n F(x_i)\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}
\]
令\(y_i=\frac{F(x_i)}{\prod \limits_{j\ne i} (x_j-x_i)}\)。
于是有
\[
F(x)=\sum_{i=0}^n y_i\prod_{j\ne i}(x-x_j)
\]
分治，从中间劈开，发现分成了两个形态类似的东西，就没了。
然而还有一个问题没有解决：\(y_i\)怎么求？
令\(G(x)=\prod\limits_{i=0}^n (x_i-x)\)，那么我们要求的就是\([G(x)/(x_i-x)]_{x_i}\)。这东西用洛必达法则得到它在\(x_i\)的极限是\(G'(x_i)\)。
求出\(G'(x)\)之后再做个多点求值就没了。
复杂度\(O(n\log^2 n)\)。
（这种东西考场基本不可能写吧……知道就行了吧……）
例题
求\(n\)的分拆数。
五边形数，大家都会。
当然，在模数比较正常的时候用生成函数硬推然后exp也是可以的。
\([\ln(1-x)]'=-\frac 1 {1-x}=-\sum_i x^i\)，两边同时积分得到
\[
\ln(1-x)=-\sum_{i=1}^{\infty} \frac{x^i}{i}
\]
某题
给定\(a_i\)，求一组\(x_i\)，满足\(0\le k\le n-1\)时\(\sum_{i=1}^n x_ia_i^k=b^k\)。
注意\(x_i\)可以为负，可以不为整数。
结果对998244353取模。保证解唯一。
首先，可以看出这个如果能把方程解出来就做完了。
使用Cramer法则，得到\(x_i=\frac{D_i}{D}\)，其中\(D=\det(A)\)，\(D_i\)表示把第\(i\)列换成\(b\)之后的行列式。
注意到\(A\)和\(A_i\)都是范德蒙德矩阵，行列式是\(\prod\limits_{j<i}(a_i-a_j)\)。发现这个形式异常熟悉，和上面多项式多点插值一模一样，所以可以套用上面的做法，于是就做完了。
某题
已知
\[
f(x)=\prod (1+a_ix)\\
g(x)=\prod (1+b_ix)\\
\]
求\(h(x)=\prod \prod (1+a_ib_jx)\)的前\(K\)项。
对\(f(x)\)求\(\ln\)，得到
\[
\ln f(x)=\sum_j (-1)^{j+1}\frac{x^j}{j}\sum_i a_i^j
\]
\(g(x)\)同理。
于是我们求出了\(a,b\)的\(k\)次方和。
\[
\ln h(x)=\sum_k (-1)^{k+1}\frac{x^k}{k} \sum_{i}a_i^k\sum_j b_j^k
\]
然后就exp一下就没了。
淘汰赛
\(m=0\)的时候生成函数为\(x\)。
\(m\ge 1\)的时候考虑当前的这些人必然是由下一层的每一组的人并起来的，于是可以枚举当前分成几组，得到\(F_m(x)=\sum_{k=2}^{\infty} F_{m-1}(x)^k=\frac{F_{m-1}(x)^2}{1-F_{m-1}(x)}\)。
讲题人没给\(n\)的数据范围，我们猜它很大，但是已知\(m=15\)。
这样一来，有分母的时候自然是不能模\(x^n\)了。我们令\(F_m(x)=\frac{f_m(x)}{g_m(x)}\)，其中\(f(x),g(x)\)都没有分母。
这样一来，可以推出两个式子：
\[
f_m(x)=f_{m-1}(x)^2\\
g_m(x)=g_{m-1}(x)^2-g_{m-1}(x)f_{m-1}(x)
\]
于是我们可以得知，\(f_m(x),g_m(x)\)都是次数为\(2^{m}\)的多项式，而且\(f_m(x)=x^{2^m}\)。
我们把最后的\(g_m(x)\)求出来，问题就变成求\(\frac{1}{g_m(x)}\)的第\(n-2^m\)项。
考虑暴力求逆的过程：对于\(i\)，有
\[
\sum_{j\le n}f_jg_{i-j}=[i=0]
\]
移项，发现就是一个长度为\(2^m\)的线性递推式，就可以快速幂+多项式取模。