普通生成函数
常用于解决组合问题。
对于无穷数列 \(a\)，生成函数即为 \(f(x)=\sum_{i=0}^{∞} a_ix^i\)。
容易发现一个显然的性质：若 \(c_i=a_i+b_i\)，那么有 \(f_c(x)=f_a(x)+f_b(x)\)。
以下是常见的生成函数：
-
\(a_i=1\)，\(f(x)=\frac{1}{1-x}\)
-
\(a_i=C_{n}^{i}\)，\(f(x)=(1+x)^n\)
-
\(a_i=[2\mid i]\)，\(f(x)=\dfrac{1}{1-x^2}\)
-
\(a_i=C_{n+i}^{n}\)，\(f(x)=(1-x)^{n+1}\)
以 LG2000 拯救世界 为例。
lzn：
金神石：\(x^0+x^6+x^{12}...=\dfrac{1}{1-x^6}\)
木神石：\(x^0+x^1+...+x^9=\frac{1-x^{10}}{1-x}\)
水神石：\(x^0+x^1+...+x^5=\frac{1-x^{6}}{1-x}\)
火神石：\(x^0+x^4+x^8...=\dfrac{1}{1-x^4}\)
土神石：\(x^0+x^1+...+x^7=\frac{1-x^{7}}{1-x}\)
kkk:
金神石：\(x^0+x^2+x^{4}...=\dfrac{1}{1-x^2}\)
木神石：\(x^0+x^1=\frac{1-x^{2}}{1-x}\)
水神石：\(x^0+x^{8}+x^{16}+...=\dfrac{1}{1-x^8}\)
火神石：\(x^0+x^{10}+x^{2-}...=\dfrac{1}{1-x^{10}}\)
土神石：\(x^0+x^1+x^2+x^3=\frac{1-x^{4}}{1-x}\)
最后连乘得到答案的生成函数是 \(\dfrac{1}{(1-x)^5}\)
根据上面的常见生成函数，易知答案函数 \(f(x)=C_{n+4}^{n}=C_{n+4}^4\)
如何求斐波那契通项公式：
\(f_0=0,f_1=1,F(x)=\sum f_ix^i\)。
因为 \(f_i=f_{i-1}+f_{i-2}~~(i\ge2)\)。
\(f_ix^i=xf_{i-1}x^{i-1}+x^2f_{i-2}x^{i-2}\)
累加得 \(F(x)=x+xF(x)+x^2F(x)\)
所以有 \(F(x)=\dfrac{x}{1-x-x^2}\)
考虑如何反推出原函数，由 性质 考虑将 \(F(x)\) 拆分。
\((1-x-x^2)=(1-\alpha)(1-\beta)\)
\(\dfrac{x}{1-x-x^2}=\dfrac{c}{1-\alpha}+\dfrac{d}{1-\beta}\)
最后求解出 \(c,d,\alpha,\beta\) 即可。
指数生成函数
常用于解决排列问题。
\(f(x)=\sum a_i\frac{x^i}{i!}\)。
-
\(a_i=1\)，\(f(x)=e^x\)
-
\(a_i=k\)，\(f(x)=e^{kx}\)
-
\(a_i=(-1)^i\)，\(f(x)=e^{-x}\)
-
\(a_i=[2\mid i]\)，\(f(x)=\frac{e^{x}+e^{-x}}{2}\)（\(x+(-x)=0\)）
-
\(a_i=[3\mid i]\)，\(f(x)=\frac{e^x+e^{\omega x}+e^{\omega^2}}{3}\)（\(1+\omega+\omega^2=0\)）
以 UOJ450 为例
分 \(d=1,2,3\) 分别考虑。
-
\(d=1\)，答案就是 \(k^n\)。
-
\(d=2\)，每个复读机的生成函数为 \(\frac{e^x+e^{-x}}{2}\)。那么答案的生成函数就是 \(2^{-k}(\frac{e^x+e^{-x}}{2})^k\)。二项式展开得 \(\sum C^{i}_{k}(e^{x})^i*(e^{-x})^{k-i}=\sum C_{k}^{i}e^{(2i-k)x}\)，然后我们将它还原成原数列求第 \(n\) 项值得答案为 \(2^{-k}\sum C_{k}^{i}(2i-k)^n\)
-
\(d=3\)，类比 \(d=2\)。