最近没什么心情更新博客，原来的文章可能永远都不会修改
由于学校组合数学课即将学到拉反，所以预习一下
拉反的描述：给定一个形式幂级数\(F(x)\)满足方程关系\(x=\frac{F(x)}{G(F(X))}\)，它是代数组合学最重要的定理之一。
\(F\)可能没有解析解，有时我们想要求出\(F\)的某项系数可以使用拉反（必须满足\(G\)的常数项为\(0\)）：\([x^n]H(F(x))=\frac{1}{n}[x^{n-1}]H'(x)G(x)^n\)
拉反存在解析和组合证明，但是这里先不写（而且组合证明考试也不会考）。
应用：例1：数列\(\{a_i\}\)满足\(a_0=1,a_{n+1}=\sum_{i+j+k=n}a_i+a_j+a_k\)，求\(a_n\)
解：假设\(a\)的母函数为\(F(x)\)，根据题意有\(F(x)=xF(x)^3+1,\frac{F(x)-1}{F(x)^3}=x\)
令\(G(x)=F(x)-1\)，得到\(\frac{G(x)}{(G(x)+1)^3}=x\)。由于\(a_0=1,[x^0]G(x)=0\)
根据拉反令\(H(x)=1\)，得知\([x^n]G(x)=\frac{1}{n}[x^{n-1}](x+1)^{3n}=\frac{1}{n}\binom{3n}{n-1}\)
例2（ABC222H）：转化后得到方程\(F=x(F+(F+1)^2)^2\)
所以\(\frac{F}{(F+(F+1)^2)^2}\)，根据拉反得知\([x^n]F(x)=\frac{1}{n}[x^{n-1}](x+(x+1)^2)^{2n}\)
\(=\frac{1}{n}[x^{n-1}]\sum_{i=0}^{2n}\binom{2n}{i}x^i(x+1)^{4n-2i}\)
\(=\frac{1}{n}\sum_{i=0}^{2n}\binom{2n}{i}[x^{n-1}]x^i(x+1)^{4n-2i}\)
\(=\frac{1}{n}\sum_{i=0}^{n-1}\binom{2n}{i}[x^{n-1-i}](x+1)^{4n-2i}\)
\(=\frac{1}{n}\sum_{i=0}^{n-1}\binom{2n}{i}\binom{4n-2i}{n-1-i}\)，显然可以在\(O(n)\)时间内计算。
例3：证明\((a+b)(a+b+n)^{n-1}=\sum_{k=0}^n\binom{n}{k}a(a+k)^{k-1}b(b+n-k)^{n-k-1}\)
考虑计算\(e^{(a+b)F(x)}\)，\(F(x)=xe^{F(x)}\)
首先把\(e^{(a+b)F(x)}\)当做一个整体运用拉反，得到\([x^n]e^{(a+b)F(x)}=\frac{1}{n}[x^{n-1}](a+b)e^{(a+b)x}e^{nx}\)
\(=\frac{1}{n}[x^{n-1}](a+b)e^{(a+b+n)x}=\frac{1}{n}(a+b)(a+b+n)^{n-1}\frac{1}{(n-1)!}\)
然后显然\(e^{(a+b)F(x)}=e^{aF(x)}e^{bF(x)}\)
\([x^n]e^{aF(x)}e^{bF(x)}=\sum_{i=0}^n([x^i]e^{aF(x)})([x^{n-i}]e^{bF(x)})\)
首先计算\([x^i]e^{aF(x)}\)，根据拉反可以得到\([x^i]e^{aF(x)}=\frac{1}{i}[x^{i-1}]\)
例4：证明
