普通生成函数是让一个序列(可以是有限序列,可以是无限序列)的第 \(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}\)。
证明可以使用广义二项式定理:
同理,\(\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\) 的通项公式。
把 \(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\) 的通项公式。
这个时候可以去想待定系数法拆分 \(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)\) 再去计算封闭式。
\(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^+\) 时的极限。
为了让 \(H(0)\) 和 \(H_0\) 的值一样,\(H(x)=\frac{1-\sqrt{1-4x}}{2x}\)。
使用广义二项式定理展开 \(\sqrt{1-4x}\)。
接下来去化简 \((\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}\)。
生成函数的展开式是多项式,生成函数的乘积就是多项式的卷积。我们知道,背包是多项式的加法卷积,所以可以使用生成函数来计算背包问题。
- 第一种金神石的块数必须是 \(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\) 项系数。
要使 \(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\) 很大,\(|a-b|\) 很小,原式就是杨辉三角上的半行减去 \(a\) 到中间那一段。
由于模数非质数,需要 exLucas 计算组合数。
\(n\ge3\),集合 \(A\subseteq[1,2,\ldots,n]\),若 \(\sum\limits_{i\in A}i\) 为奇数,那么称 \(A\) 为奇集合。集合 \(S\) 为所有奇集合组成的集合。求 \(|S|\),以及 \(\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\) 贡献,得到奇集合和非奇集合的数量是相等的,即 \(|S|=\frac12\times2^n=2^{n-1}\)。
带入 \(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}\)。