不得不说这个东西真是妙啊
遭到了降智打击
生成函数又叫做母函数，主要用于解决一些组合数学问题
对于一个数列\(\{f_0,f_1,f_2,...,f_n\}\)
我们定义其生成函数为
\[F(x)=f_0+f_1x+f_2x^2+...+f_nx^n\]
也就是
\[F(x)=\sum_{i=0}^nf_ix^i\]
也就是把数列的每一项当成了多项式对应项的系数
$$$$
既然是函数，那么我们就可以去计算对应的函数值
比如一个数列
\[\{1,1,1,1,1,1...\}\]
它的生成函数
\[F(x)=1+x+x^2+x^3+...\]
发现这是一个无穷等比数列
于是
\[F(x)=\frac{1-x^n}{1-x}\]
对于\(x\in (-1,1)\)，当\(n\)趋于无穷的时候，\(x^n=0\)
于是
\[F(x)=\frac{1}{1-x}\]
对于一些特殊的数列，比如说
\[\{1,0,1,0,1,0,1,0,1...\}\]
也就是\(mod\ 2=0\)的项为\(1\)，其余项为\(0\)
也就是
\[F(x)=x+x^2+x^4+...\]
简单换一下元，就会发现\(F(x)=\frac{1}{1-x^2}\)
于是我们可以发现生成函数
\[F(x)=\frac{1}{1-x^k}\]
对应的数列是一个\(k\)的倍数项为\(1\)，其余项为\(0\)的数列
$$$$
这样看也没什么用啊，怎么能跟组合计数有关系呢
我们都学过多项式，我们知道我们可以用多项式的系数来表示方案数
我们来考虑一个最简单多项式
\[A=1+x+x^2+x^3+...\]
\(A\)的第\(i\)项可以表示选取\(i\)个物品的方案数
写成生成函数\(F(x)=\frac{1}{1-x}\)
那么\(A^k\)就表示从\(A\)中进行\(k\)次选取的方案数，第\(i\)项就是选出\(i\)个物品的方案数
那么这个生成函数相乘表示什么呢
\[F^k(x)=\frac{1}{(1-x)^k}\]
而
\[A^k=\sum_{i=0}\binom{i-1+k}{k-1}x^i\]
这就是一个组合数插板就得出来了
根据我不知道的广义二项式定理，上面的式子是相等的
于是我们得出一个重要结论
多项式的卷积对应的就是两个生成函数的乘积
$$$$
之后我们真的可以来做一道题了
LGP2000
先把所有的限制条件变成多项式和生成函数
必须是6的倍数，那么就是\(F(x)=\frac{1}{1-x^6}\)
最多用\(9\)块，也就是一个只有前\(10\)项系数为\(1\)的多项式，一个等比数列求和，\(F(x)=\frac{1-x^{10}}{1-x}\)
最多用5块，\(F(x)=\frac{1-x^{6}}{1-x}\)
必须是4的倍数，\(F(x)=\frac{1}{1-x^4}\)
剩下的就不写了，就是把每一个条件都抽象成生成函数，之后对这些个生成函数求一个乘积，发现是\(F(x)=\frac{1}{(1-x)^5}\)
我们把这个转化成多项式
\[\sum_{i=0}\binom{i-1+5}{5-1}x^i\]
我们要的是第\(n\)项系数，也就是\(\binom{n+4}{4}\)这就是答案了
$$$$
生成函数更神仙的地方就在于推通项了
比如说\(fib\)数列
\[fib_n=\begin{cases}1&n\leq2\\fib_{n-1}+fib_{n-2}&n>2\end{cases}\]
其生成函数为
\[\begin{aligned} F(x)=&\sum_{i=1}fib_ix^i\\&=\sum_{i=1}(fib_{i-1}+fib_{i-2}+[i=1])x^i\\&=\sum_{i=1}fib_{i-1}x^i+\sum_{i=1}fib_{i-2}x^i+x\\&=x\sum_{i=1}fib_{i-1}x^{i-1}+x^2\sum_{i=1}fib_{i-2}x^{i-2}+x\\\end{aligned}\]
发现这个\(\sum_{i=1}fib_{i-1}x^{i-1}\)和\(\sum_{i=1}fib_{i-2}x^{i-2}\)不都是\(F(x)\)吗
于是就有
\[F(x)=xF(x)+x^2F(x)+x\]
于是我们可以求得
\[F(x)=\frac{x}{1-x-x^2}\]
这就是\(fib\)数列的生成函数了
但是这有什么用呢
可以求通项啊
我们把分母上的\(1-x-x^2\)因式分解一下
\[F(x)=\frac{x}{(1-\frac{1-\sqrt5}{2}x)(1-\frac{1+\sqrt5}{2}x)}\]
在搞一搞
\[F(x)=-\frac{1}{\sqrt5}\frac{1}{(1-\frac{1-\sqrt5}{2}x)} + \frac{1}{\sqrt5}\frac{1}{(1-\frac{1+\sqrt5}{2}x)}\]
发现出现了诸如\(\frac{1}{1-cx}\)这样的生成函数
我们知道这样的生成函数对应的多项式应该形如\(\sum_{i=1}c^ix^i\)
所以就会有
\[fib_n=-\frac{1}{\sqrt5}(\frac{1-\sqrt5}{2})^n+\frac{1}{\sqrt5}(\frac{1+\sqrt5}{2})^n\]
真是优雅自然
我们再来推一个难一点的数列，卡特兰数
卡特兰有一个递推式是这个样子的
\[f_n=\begin{cases}1&n=0\\\sum_{i=0}^{n-1}f_if_{n-i-1}&n>0\end{cases}\]
我们照样来推一下
\[\begin{aligned} F(x)&=\sum_{i=0}(\sum_{j=0}^{i-1}f_jf_{i-j-1}+[i=0])x^i\\&=1+\sum_{i=1}(\sum_{j=0}^{i-1}f_jf_{i-j-1})x^i\\&=1+x\sum_{i=1}(\sum_{j=0}^{i-1}f_jf_{i-j-1})x^{i-1}\end{aligned}\]
考虑把\(x^{i-1}\)分成\(x^{j}\times x^{i-j-1}\)，之后分进去
就是
\[\begin{aligned} F(x)&=1+x\sum_{i=1}\sum_{j=0}^{i-1}f_jx^j\times f_{i-j-1}x^{i-j-1}\end{aligned}\]
惊奇的发现\(f_jx^j\)是对应多项式的\(j\)次项，\(f_{i-j-1}x^{i-j-1}\)是对应多项式的\(i-j-1\)次项，于是内部还是一个卷积的形式也就是卡特兰数自己卷自己，就是\(F^2(x)\)
于是
\[F(x)=1+xF^2(x)\]
这不是一元二次方程吗，解一下这个方程
发现
\[F(x)=\frac{1\pm \sqrt{1-4x}}{2x}\]
发现竟然有一个正负号的问题
分式方程不好解我们上整式方程
设\(k=\frac{1\pm \sqrt{1-4x}}{2x}\)
\[2xk\pm \sqrt{1-4x}=1\]
尽管生成函数的\(x\)没有什么意义，但是我们带入\(x=0\)的时候，\(F(0)=f_0\)，这是非常显然的
于是
\[2\times 0\times 0\pm1=0\]
显然那个符号应该是正，由于这是移项过来的，于是在那边应该是个负号，所以
\[F(x)=\frac{1-\sqrt{1-4x}}{2x}\]
这个东西有什么用呢，可以搞卡特兰数的通项！
我们发现那个\(\sqrt{1-4x}\)就是\((1-4x)^{\frac{1}{2}}\)，尝试二项式定理
\[(1-4x)^{\frac{1}{2}}=\sum_{i=0}\binom{\frac{1}{2}}{i}(-4x)^i\]
推不动了，先弃疗了
$$$$
来一道神仙题
[TJOI2015]概率论
感性理解一下这个\(n\)个节点的二叉树同构的数量就是\(f_n\)，卡特兰数
现在的问题就是求一个分子，就是所有\(n\)个节点的二叉树的同构的叶子节点的个数
我们设为\(h_n\)
答案就是\(\frac{h_n}{f_n}\)
我们考虑一下\(h_n\)如何求
显然我们可以利用一个类似卡特兰的转移
\[h_i=\sum_{i=0}^{j-1}h_jf_{i-j-1}+h_{i-j-1}f_j\]
就是枚举左右儿子的节点个数，之后由于要和另一个儿子组合，于是得乘上方案数
于是现在可以去写一个\(O(n^2)\)的了
f[0]=1,f[1]=1;for(re int i=2;i<=n;i++)for(re int j=0;j<i;j++) f[i]+=f[j]*f[i-j-1];h[0]=0,h[1]=1;for(re int i=2;i<=n;i++)for(re int j=0;j<i;j++) h[i]+=f[i-j-1]*h[j]+f[j]*h[i-j-1];printf("%.12lf",double(h[n])/double(f[n]));考虑到这个形式我们并不是很好化简，于是考虑到\(f_jh_{i-j-1}\)会被算到两次
于是直接写成
\[h_i=2\sum_{i=0}^{j-1}h_jf_{i-j-1}\]
我们得特殊定义一下\(h_1=1\)
考虑求这个函数的生成函数
\[\begin{aligned}F(x)=&\sum_{i=1}(2\sum_{j=0}^{i-1}h_jf_{i-j-1}+[i=1])x^i\\&=x+\sum_{i=1}(2\sum_{j=0}^{i-1}h_jf_{i-j-1})x^i\\&=x+x\sum_{i=1}(2\sum_{j=0}^{i-1}h_jf_{i-j-1})x^{i-1}\\&=x+x\sum_{i=1}2\sum_{j=0}^{i-1}h_jx_j\times f_{i-j-1}x^{i-j-1}\end{aligned}\]
设\(G(x)=\sum_{i=0}f_ix^i\)
于是
\[\begin{aligned}F(x)=&x+2xF(x)G(x)\end{aligned}\]
我们知道\(G(x)=\frac{1-\sqrt{1-4x}}{2x}\)
于是我们可以解得
\[F(x)=\frac{x}{\sqrt{1-4x}}\]
之后我就又不会做了，愉快地去看题解，发现果真还是菜啊
并不会求导，于是只能复述一下题解
对\(xG(x)\)求导，发现
\[(xG(x))'=\frac{1}{\sqrt{1-4x}}=\frac{F(x)}{x}\]
据说\(xG(x)\)求导之后每一项从\(f_ix^{i+1}\)变成了\((i+1)f_ix^i\)
就等于对应的\(\frac{F(x)}{x}\)的每一项\(h_ix^{i-1}\)，也就是\(h_{i+1}x^i\)
也就是说我们得到了
\[h_{i+1}x^{i}=(i+1)f_ix^i\]
就是
\[h_{i+1}=(i+1)f_i\]
所以\(h_i=if_{i-1}\)
之后我们的答案就是
\[\frac{nf_{n-1}}{f_n}\]
我们利用卡特兰数的通项公式\(f_n=\frac{1}{n+1}\binom{2n}{n}\)
于是
\[\begin{aligned}\frac{nf_{n-1}}{f_n}&=\frac{n\frac{1}{n}\binom{2n-2}{n-1}}{\frac{1}{n+1}\binom{2n}{n}}\\&=\frac{(n+1)\frac{(2n-2)!}{(n-1)!(n-1)!}}{\frac{(2n)!}{n!n!}}\\&=\frac{(2n-2)!n!n!(n+1)}{(2n)!(n-1)!(n-1)!}\\&=\frac{n^2(n+1)}{2n(2n-1)}=\frac{n(n+1)}{2(2n-1)}\end{aligned}\]
于是一行就写完了
#include<cstdio>
int main() {double n;scanf("%lf",&n);printf("%.12lf\n",n*(n+1)/2/(2*n-1));}这道题没能推出通项不是很得劲，[国家集训队]整数的lqp拆分可以用生成函数推出通项来
我又来写概率生成函数了
感觉这个东西很玄幻啊
对于一个取值范围为非负整数的离散随机变量\(X\)，我们定义其概率生成函数\(F(x)\)为
\[F(x)=\sum_{i=0}^{\infty}P(X=i)x^i\]
也就是第\(i\)项的系数就是这个离散变量取到\(i\)的概率
于是就有两个非常显然的性质
我们令\(x=1\)
\[F(1)=\sum_{i=0}^{\infty}P(X=i)=1\]
另一个性质，我们求一下导
\[F'(x)=\sum_{i=1}^{\infty}iP(X=i)x^{i-1}\]
继续带入\(x=1\)
惊奇的发现\(E(X)=F'(1)\)，因为\(iP(X=i)\)这样累加起来显然就是期望值了
来看一道经典的例题[CTSC2006]歌唱王国
我们定义\(f_i\)表示这个字符串在第\(i\)项结束的概率，我们再定义\(g_i\)表示到了第\(i\)项还没有结束的概率，\(F(x),G(x)\)分别为这两个序列的概率生成函数
显然存在一条性质\(g_{i-1}=f_{i}+g_{i}\)，就是在\(i-1\)还没有结束的概率就等于\(i\)点结束或者不结束的概率之和
我们用下一个点结束或者不结束的概率之和
我们用生成函数来写这个柿子就是
\[1+xG(x)=G(x)+F(x)\]
求一个导，右边是\(G'(x)+F'(x)\)
左边的常数项求导玩就没了，于是对\(xG(x)\)求导
\[(xG(x))'=\sum_{i=0}^{\infty}(i+1)g_ix^{i+1-1}=\sum_{i=0}^{\infty}g_ix^i+\sum_{i=0}^{\infty}ig_ix^{i-1+1}=G(x)+xG'(x)\]
于是
\[G'(x)+F'(x)=G(x)+xG'(x)\]
当\(x=1\)时就有\(F'(x)=G(x)=E(x)\)
于是我们只需要求一个\(G(x)\)就好了
之后就会这样一个柿子
\[G(x)(\frac{1}{m}x)^L=\sum_{i=1}^La_iF(x)(\frac{1}{m}x)^{L-i}\]
其中\(a_i\)表示\(i\)前缀是否是一个\(boder\)
看起来有点吓人啊，但是我们可以这样来理解
\(G(x)\)显然是对应了一个还没有结束的任意字符串，我们在后面补上一个原串，得到一个长度增加了\(L\)的新串，显然这个新串是一定可以结束的，得到这样一个新串的概率显然就是\(G(x)\times \frac{1}{m^L}\)
由于我们强行补上这个新串，这个时候游戏一定结束了，但是很有可能游戏在这之前就已经结束了
我们考虑一下如果当前已经添加了\(i\)个字符游戏结束的情况，显然这\(i\)字符既是原串的前缀也是原串的一个后缀，也就是我们经常说的\(boder\)
于是如果\(i\)是一个\(boder\)的话，我们得来的这个字符串就相当于在长度增加了\(i\)的时候已经结束的了一个字符串又钦定了\(L-i\)个字符
这样就得到了上面的柿子
我们代入\(x=1\)试试看，发现
\[G(1)=\sum_{i=1}^La_im^i\]
我们要求的是啥来着，不就是\(E(x)=G(1)\)吗，于是我们现在直接\(O(L)\)的时间算出\(G(1)\)就好了
代码
#include<cstdio>
#define re register
const int maxn=1e5+5;
const int mod=10000;
int T,pw[maxn],ans,a[maxn],nx[maxn],m,n;
int main() {scanf("%d%d",&m,&T);pw[0]=1;for(re int i=1;i<maxn;i++) pw[i]=1ll*pw[i-1]*m%mod;while(T--) {scanf("%d",&n);ans=0;for(re int i=1;i<=n;i++) scanf("%d",&a[i]);for(re int i=2;i<=n;i++) {nx[i]=0;int p=nx[i-1];while(p&&a[i]!=a[p+1]) p=nx[p];nx[i]=p+(a[i]==a[p+1]);}while(n) ans=(ans+pw[n])%mod,n=nx[n];if(ans<1000) putchar('0');if(ans<100) putchar('0');if(ans<10) putchar('0');printf("%d\n",ans);}return 0;
}
