主要参考自《生成函数的运算与应用(金策15年wc营员交流)》,《生成函数的运算与组合计数问题(金策15年集训队论文)》和miskcoo的blog

多项式的定义

FFT与NTT解决多项式乘法。

http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-15

bzoj4827: [Hnoi2017]礼物
这道题大概就是将要求的多个答案看成一个数列,就会发现这是个卷积。FFT搞一搞就行。

NTT模数表

http://blog.miskcoo.com/2014/07/fft-prime-table

多项式除法及取模

http://blog.miskcoo.com/2015/05/polynomial-division

大致思想就是利用反转消去余数的影响,然后直接上求逆即可


多项式求逆

http://blog.miskcoo.com/2015/05/polynomial-inverse
例题:bzoj4555
这道题将斯特林数变为组合数后,很容易发现是可以化成一个卷积的。然后就可以NTT了。
然后多项式求逆做法就是,考虑后面那个sigma的意义,推出递推式,然后将他表示成另一个多项式的逆,就ok了。


集合的生成函数

序列的EGF/OGF:
$$
\sum_{i>=0}A^{i}=\frac{1}{1-A}
$$
集合的EGF:
$$
\sum_{i>=0}\frac{A^{i}}{i!}=e^A
$$

一些结论
$$
\frac{1}{(1-x)^{n+1}}=\sum_{i>=0}\binom{n+i}{n}x^i
$$


求ln

求个导,就相当于求个逆元后再求积分了


求exp

分治fft方法

$$
B(x)=exp(A(x))
\\
B’(x)=B(x)A’(x)
$$
比较系数得到
$$
b_{0}=1
\\
b_{i}=\frac{1}{i}\sum_{1<=k<=i}ka_{k}b_{i-k} (i>=1)
$$
$b_{0}=1$ 可以由泰勒展开看出,这里泰勒可以先代$e^x$,再将$A(x)$代进去


牛顿迭代法

$f(x) \equiv f_{0}(x) (mod x^n)$
$0=g(f(x)) \equiv g(f_{0}(x))+g’(f_{0}(x))(f(x)-f(x_{0})) (mod x^n)$
$$f(x)\equiv -\frac{g(f_{0}(x))}{g’(f_{0}(x))}+f(x_{0})$$
一定要注意到是对F(x)微分!

用牛迭来推一下求逆:
构造$g(f(x))=\frac{1}{f(x)}-A(x)=0$
$$\begin{eqnarray} f(x) & \equiv & f_{0}(x) (mod x^n) \\
\rightarrow f(x) & \equiv & -\frac{\frac{1}{f_{0}(x)}-A(x)}{-\frac{1}{f_{0}(x)^2}}+f_{0}(x) (mod x^{2n}) \ \rightarrow f(x) & \equiv & 2f_{0}(x)-A(x)f_{0}(x)^2 (mod x^{2n}) \end{eqnarray}$$

用牛迭来推一下开根
构造$g(f(x))=f(x)^2-A(x)=0$
$$\begin{eqnarray} f(x) & \equiv & f_{0}(x) (mod x^n) \\
\rightarrow f(x) & \equiv & -\frac{f_{0}(x)^2-A(x)}{2f_{0}(x)}+f_{0}(x) (mod x^{2n}) \ \rightarrow f(x) & \equiv & \frac{f_{0}(x)^2+A(x)}{2f_{0}(x)} (mod x^{2n}) \end{eqnarray}$$


利用exp和ln可以用来做k次幂,k次方等问题了

作对数运算时常数项一定要为1!
作指数运算时常数项一定要为0!


完全背包计数与01背包计数

利用对数函数化乘为加
化为$\sum_{i=1}^{n}A(x^i)$的形式,有用的只有nlogn个


拉格朗日反演

http://users.math.msu.edu/users/magyar/Math880/Lagrange.pdf

$$[x^n]g(x)=\frac{1}{n}[x^{-1}]\frac{1}{f(x)^n}$$

证明:
$$x=g(f(x))=\sum_{i\ge 1}b_if(x)^i \\
1=\sum_{i\ge1}ib_if(x)^{i-1}f’(x) \\
\frac{1}{f(x)^n}=\sum_{i=1}^{n-1}\frac{ib_i}{i-n}(f(x)^{i-n})’+nb_n\frac{f’(x)}{f(x)}+\sum_{i> n}\frac{ib_i}{i-n}(f(x)^{i-n})’.$$

$$\begin{align}\frac{f’(x)}{f(x)}&=\frac{a_1+2a_2x+3a_3x^2+\cdots}{a_1x+a_2x^2+\cdots}\\
&=\frac{a_1+2a_2x+3a_3x^2+\cdots}{a_1x}\cdot \frac{1}{1+\left(\frac{a_2}{a_1}x+\frac{a_3}{a_1}x^2+\cdots\right)}\ &=\left(x^{-1}+\frac{2a_2}{a_1}+\cdots\right)\left(1-z\left(\frac{a_2}{a_1}+\frac{a_3}{a_1}x+\cdots\right)\right) \end{align}.$$

$$\therefore[x^{-1}]\frac{f’(x)}{f(x)}=1.$$
$$\therefore[x^{-1}]\frac{1}{f(x)^n}=n*b_{n}.$$

拉格朗日反演的推广
$$[x^n]h(g(x))=\frac{1}{n}[x^{-1}]\frac{h’(x)}{f(x)^n}$$