普通生成函数

普通生成函数是让一个序列（可以是有限序列，可以是无限序列）的第 $i$ 项 $a_i(i\ge0)$ 作为 $x^i$ 的系数。
序列 $[2,3,4,5]$ 用生成函数表达就是 $2+3x+4x^2+5x^3$。
序列 $[1,3,5,7,\ldots]$ 用生成函数表达就是 $\sum\limits_ {i=0}^\infty(2i+1)x^i$。

由于这样的生成函数是个多项式，不便计算，所以有些生成函数具有封闭形式。
封闭形式可以通过方程，数列知识等来计算，计算时，要认为生成函数中的 $x$ 是个极小值，并且算出来是收敛的。
如 $F(x)=\sum\limits_ {i=0}^\infty x^i=\frac 1{1-x}$ 就是用等比数列求和，或者说几何级数得到的。
那要是是 $\sum\limits_{i=0}^\infty(i+1)x^i$ 甚至是 $\sum\limits_{i=0}^\infty\binom{n+i-1}ix^i$ 呢？
答案是 $\sum\limits_{i=0}^\infty\binom{n+i-1}ix^i=\frac1{(1-x)^n}$。
证明可以使用广义二项式定理：

\[\begin{aligned} \frac1{(1-x)^n}&=(1-x)^{-n}\\ &=\sum_{i=0}^\infty\binom{-n}i(-x)^i1^{-1-i}\\ &=\sum_{i=0}^\infty\binom{-n}i(-x)^i\\ &=\sum_{i=0}^\infty\frac{(-n)^{\underline i}}{i!}(-x)^i\\ &=\sum_{i=0}^\infty(-1)^i\binom{n+i-1}i(-x)^i\\ &=\sum_{i=0}^\infty\binom{n+i-1}ix^i\\ \end{aligned}\]

同理，$\sum\limits_{i=0}^\infty\binom{n+i-1}it^ix^i=\frac1{(1-tx)^n}$。
根据二项式定理，$\sum\limits_{i=0}^n\binom nix^i=(1+x)^n$。
至于在 $F(x)$ 展开式前加了 $t$ 个 $0$，就相当于乘以了 $x^t$，所以添加后就是 $x^tF(x)$。

生成函数最直接的用法就是求解递推式。
已知 $a_0=1,a_1=2,a_n-5a_{n-1}+6a_{n-2}=0$，求 $a_n$ 的通项公式。

\[\begin{aligned} F(x)=\sum\limits_{i=0}^\infty a_ix^i=a_0+a_1x+a_2x^2&+a_3x^3+\ldots\\ -5F(x)=-5x\sum\limits_{i=0}^\infty a_ix^i=-5a_0x-5a_1x^2&-5a_2x^3-5a_3x^4-\ldots\\ 6x^2F(x)=-5x\sum\limits_{i=0}^\infty a_ix^i=6a_0x^2&+6a_1x^3+6a_2x^4+6a_3x^5-\ldots\\ F(x)-5xF(x)+6x^2F(x)=a_0+(a_1-5a_0)x\\ \end{aligned}\]

把 $a_0=1,a_1=2$ 带入得到 $F(x)-5xF(x)+6x^2F(x)=1-3x$，即 $F(x)=\frac{1-3x}{x^2-5x+6}=\frac1{1-2x}$。

运用广义二项式定理展开 $\frac1{1-2x}$，得到 $F(x)=\sum\limits_{i=0}^\infty2^ix^i$，也就是说 $a_n=2^n$。

上面是侥幸把封闭式的分子约分成了 $1$，但往往是做不到的。
比如斐波那契数列 $f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}$，求 $f_n$ 的通项公式。

\[\begin{aligned} F(x)=\sum\limits_{i=0}^\infty f_ix^i=f_0+f_1x+f_2x^2&+f_3x^3+\ldots\\ xF(x)=x\sum\limits_{i=0}^\infty f_ix^i=f_0x+f_1x^2&+f_2x^3+f_3x^4+\ldots\\ x^2F(x)=x^2\sum\limits_{i=0}^\infty f_ix^i=f_0x^2&+f_1x^3+f_2x^4+f_3x^5+\ldots\\ F(x)-xF(x)-x^2F(x)=f_0+(f_1-f_0)x\\ F(x)=\frac x{1-x-x^2}\\ \end{aligned}\]

这个时候可以去想待定系数法拆分 $F(x)$。

\[\frac x{1-x-x^2}=\frac A{1-ax}+\frac B{1-bx}=\frac{(-aB-Ab)x+A+B}{abx^2-(a+b)x+1}\] \[\begin{cases} -aB-Ab=1\\ A+B=0\\ ab=-1\\ a+b=1 \end{cases}\]

$4$ 个方程，$4$ 个未知数，由于 $A,B$ 和 $a,b$ 地位相同，钦定 $A\ge B$。

\[\begin{cases} A=\frac1{\sqrt5}\\ B=-\frac1{\sqrt5}\\ a=\frac{1+\sqrt5}2\\ b=\frac{1-\sqrt5}2 \end{cases}\] \[\begin{aligned} \frac x{1-x-x^2}&=\frac{\frac1{\sqrt5}}{1-\frac{1+\sqrt5}2x}+\frac{-\frac1{\sqrt5}}{1-\frac{1-\sqrt5}2x}\\ &=\frac1{\sqrt5}(\frac1{1-\frac{1+\sqrt5}2x}-\frac1{1-\frac{1-\sqrt5}2x})\\ &=\sum_{i=0}^\infty\frac1{\sqrt5}((\frac{1+\sqrt5}2)^i-(\frac{1-\sqrt5}2)^i)x^i \end{aligned}\]

所以 $f_i=\frac1{\sqrt5}((\frac{1+\sqrt5}2)^i-(\frac{1-\sqrt5}2)^i)$。

卡特兰数的递推式 $H_n=\sum\limits_{i=0}^{n-1}H_iH_{n-i-1}$ 可以通过 dp 简单求出，其中边界 $H_0=1,H_1=1$。
卡特兰数的递推是卷积的形式，可以先计算一下 $H^2(x)$ 再去计算封闭式。

\[\begin{aligned} H^2(x)&=\sum_{i=0}^\infty(\sum_{j=0}^iH_jH_{i-j})x^i\\ &=\sum_{i=0}^\infty(\sum_{j=0}^{(i+1)-1}H_jH_{(i+1)-j-1})x^i\\ &=\sum_{i=0}^\infty H_{i+1}x^i\\ &=\frac1x\sum_{i=0}^\infty H_{i+1}x^{i+1}\\ &=\frac1x\sum_{i=1}^\infty H_ix^i\\ &=\frac1x(H_0x^0+\sum_{i=1}^\infty H_ix^i-1)\\ &=\frac1x(H(x)-1)\\ \end{aligned}\]

$xH^2(x)-H(x)+1=0$，即 $H(x)=\frac{1\pm\sqrt{1-4x}}{2x}$，有增根。
当 $x=0$ 时，$H(0)$ 的值就是 $H_0$，后面的 $H_ix^i$ 都因为 $x^i=0$ 为 $0$。
使用洛必达法则对 $H(x)$ 进行求导，来获得 $x=0^+$ 时的极限。

\[\lim_{x\to0^+}\frac{1\pm\sqrt{1-4x}}{2x}=\frac{\mp\frac2{\sqrt{1-4x}}}2=\mp\frac1{\sqrt{1-4x}}\]

为了让 $H(0)$ 和 $H_0$ 的值一样，$H(x)=\frac{1-\sqrt{1-4x}}{2x}$。
使用广义二项式定理展开 $\sqrt{1-4x}$。

\[\begin{aligned} \sqrt{1-4x}&=(1-4x)^\frac12\\ &=\sum_{i=0}^\infty\binom{\frac12}i(-4x)^i1^{\frac12-i}\\ &=\sum_{i=0}^\infty\frac{(\frac12)^{\underline i}}{i!}(-4x)^i\\ &=1+\sum_{i=1}^\infty\frac{(\frac12)^{\underline i}}{i!}(-4x)^i\\ \end{aligned}\]

接下来去化简 $(\frac12)^{\underline i}$。

\[\begin{aligned} (\frac12)^{\underline i}&=\frac12\frac{-1}2\frac{-3}2\ldots\frac{-i-3}2\\ &=\frac{(-1)^{i-1}1\times3\times5\times\ldots\times(2i-3)}{2^i}\\ &=\frac{(-1)^{i-1}(2i-2)!}{2^i(i-1)!2^{i-1}}\\ &=\frac{(-1)^{i-1}(2i-2)!}{2^{2i-1}(i-1)!}\\ \end{aligned}\] \[\begin{aligned} \sqrt{1-4x}&=1+\sum_{i=1}^\infty\frac{(\frac12)^{\underline i}}{i!}(-4x)^i\\ &=1+\sum_{i=1}^\infty\frac{\frac{(-1)^{i-1}(2i-2)!}{2^{2i-1}(i-1)!}}{i!}(-4x)^i\\ &=1-\sum_{i=1}^\infty\frac{(2i-2)!2^{2i}x^i}{2^{2i-1}(i-1)!i!}\\ &=1-\sum_{i=1}^\infty\frac{(2i-2)!}{(i-1)!i!}2x^i\\ &=1-\sum_{i=1}^\infty\frac{(2i-1)!}{(i-1)!i!}\frac1{2i-1}2x^i\\ &=1-\sum_{i=1}^\infty\binom{2i-1}i\frac1{2i-1}2x^i\\ \end{aligned}\\\] \[\begin{aligned} H(x)&=\frac{1-\sqrt{1-4x}}{2x}\\ &=\frac{1-(1-\sum\limits_{i=1}^\infty\binom{2i-1}i\frac1{2i-1}2x^i)}{2x}\\ &=\sum\limits_{i=1}^\infty\binom{2i-1}i\frac1{2i-1}x^{i-1}\\ &=\sum\limits_{i=0}^\infty\binom{2i+1}{i+1}\frac1{2i+1}x^i\\ &=\sum\limits_{i=0}^\infty\binom{2i}{i}\frac1{i+1}x^i \end{aligned}\]

最终得到 $H_n=\binom{2n}n\frac1{n+1}$。

生成函数的展开式是多项式，生成函数的乘积就是多项式的卷积。我们知道，背包是多项式的加法卷积，所以可以使用生成函数来计算背包问题。

LGP2000 拯救世界

第一种金神石的块数必须是 $6$ 的倍数，即 $\sum\limits_{i=0}^\infty x^{6i}=\frac1{1-x^6}$。
第一种木神石最多用 $9$ 块，即 $\sum\limits_{i=0}^9x^i=\frac{1-x^{10}}{1-x}$。

别的所有石头全部同理，把 $10$ 种石头的封闭式乘起来，得到 $\frac1{(1-x)^5}$。
运用广义二项式定理展开，得到 $\sum\limits_{i=0}^\infty\binom{i+4}ix^i$。
那么第 $n$ 项系数就是 $\binom{n+4}n$，不过这题要写高精度，所以我写 Python。

import decimal
decimal.getcontext().prec=400000
n=decimal.Decimal(input())
print((n+1)*(n+2)*(n+3)*(n+4)/24)

LGP3726 [AH2017/HNOI2017] 抛硬币
甲抛硬币 $a$ 次，乙抛硬币 $b$ 次，问有多少种情况使得甲的正面次数大于乙。
$a,b\le10^{15}$，$b\le a\le b+10^4$

如果甲抛出了正面就把计数器加一，如果乙抛出了正面就把计数器减一。
构造生成函数 $F(x)=(1+x)^a(1+\frac1x)^b$，那么甲正面的情况就是 $F(x)$ 的所有正指数系数和 $\sum\limits_{i=1}^a[x^i]F(x)$，$[x^i]F(x)$ 表示生成函数 $F(x)$ 的 $i$ 项系数。

\[\begin{aligned} \sum_{i=1}^a[x^i]F(x)&=\sum_{i=1}^a[x^i](1+x)^a(1+\frac1x)^b\\ &=\sum_{i=1}^a[x^i]x^a(1+\frac1x)^a(1+\frac1x)^b\\ &=\sum_{i=1}^a[x^i]x^a(1+\frac1x)^{a+b}\\ \end{aligned}\] \[\begin{aligned} x^a(1+\frac1x)^{a+b}&=x^a\sum_{i=0}^{a+b}\binom{a+b}i(\frac1x)^i1^{a+b-i}\\ &=\sum_{i=0}^{a+b}\binom{a+b}ix^{a-i} \end{aligned}\]

要使 $a-i\ge1$，也就是要做到 $i\le a-1$，即 $\sum\limits_{i=0}^{a-1}\binom{a+b}ix^{a-i}=\sum\limits_{i=1}^a\binom{a+b}{a-i}x^i$。
最后得到 $\sum\limits_{i=1}^a[x^i]F(x)=\sum\limits_{i=1}^a\binom{a+b}{a-i}=\sum\limits_{i=0}^{a-1}\binom{a+b}{i}$。
因为 $a+b$ 很大，$\vert a-b\vert$ 很小，原式就是杨辉三角上的半行减去 $a$ 到中间那一段。
由于模数非质数，需要 exLucas 计算组合数。

$n\ge3$，集合 $A\subseteq[1,2,\ldots,n]$，若 $\sum\limits_{i\in A}i$ 为奇数，那么称 $A$ 为奇集合。集合 $S$ 为所有奇集合组成的集合。求 $\vert S\vert$，以及 $\sum\limits_{A\in S}\sum\limits_{i\in A}i=\sum\limits_{A\in S}\operatorname{sum}(A)$。

答案可以乱做，猜一个奇集合数量是全集子集数量的一半 $2^{n-1}$，每个集合平均有 $\frac n2$ 个元素，每个元素平均大小 $\frac{n+1}2$，所以和是 $2^{n-1}\times\frac n2\times\frac{n+1}2=n(n+1)2^{n-3}$。猜得很准，这就是答案。

构造生成函数 $F(x)=\prod\limits_{i=1}^n(1+x^i)$。
$F(x)=\prod\limits_{i=1}^n(1+x^i)=\sum\limits_{A\subseteq[1,2,\ldots,n]}x^{\operatorname{sum}(A)}$
当 $x=-1$ 时，等式左边为 $0$，是收敛的，所以不妨把 $x=-1$ 带入。
当 $x=-1$ 时，每个奇集合会对等式右边作出 $+1$ 贡献，否则会作出 $-1$ 贡献，得到奇集合和非奇集合的数量是相等的，即 $\vert S\vert=\frac12\times2^n=2^{n-1}$。

\[\begin{aligned} \prod\limits_{i=1}^n(1+x^i)&=\sum\limits_{A\subseteq[1,2,\ldots,n]}x^{\operatorname{sum}(A)}\\ (\prod\limits_{i=1}^n(1+x^i))'&=(\sum\limits_{A\subseteq[1,2,\ldots,n]}x^{\operatorname{sum}(A)})'\\ \sum_{i=1}^n{ix^{i-1}\prod_{j\ne i}{\left( 1+x^j \right)}}&=\sum\limits_{A\subseteq[1,2,\ldots,n]}\operatorname{sum}(A)x^{\operatorname{sum}(A)-1} \end{aligned}\]

带入 $x=-1$，得到 $\sum\limits_{A\in S}\operatorname{sum}(A)=\sum\limits_{A\not\in S}\operatorname{sum}(A)$。
带入 $x=1$，得到 $\sum\limits_{A\in S}\operatorname{sum}(A)+\sum\limits_{A\not\in S}\operatorname{sum}(A)=n(n+1)2^{n-2}$。
最后得到 $\sum\limits_{A\in S}\operatorname{sum}(A)=\frac12\times n(n+1)2^{n-2}=n(n+1)2^{n-3}$。