生成函数入门

· · 题解

Part1 前言

什么？我只会数据结构？不会生成函数怎么办啊！

虽然多项式已经“滚出 NOI”了，但它很有利于理解生成函数，毕竟考试要是正解生成函数只是放暴力卷积过呢？

Part2 形式及含义

给定数列 a_i，它的普通生成函数为 \sum\limits_{i=0}^\infty a_ix^i，指数生成函数为 \sum\limits_{i=0}^\infty\dfrac{a_i}{i!}x^i。

对于数列 a_i=1，它的普通生成函数为 \sum\limits_{i=0}^\infty x^i=\dfrac1{1+x}，注意左式只有 |x|<1 才是收敛的，右式称为形式幂级数，只有左式收敛才能与右式对应。

它的指数生成函数为 \sum\limits_{i=0}^\infty\dfrac{x^i}{i!}=e^x，这一步可以直接右式泰勒展开得到左式。

Part3 问题转化

对于这类题，我们可以先想一想能否得到与答案类似的东西。

比如，设 g_n 表示 n 个节点有标号无向图个数，显然有 g_n=2^{\frac{n(n-1)}2}。

但这并不是我们想要得到的答案，设 f_n 表示 n 个点有标号无向连通图个数，考虑 1 所在连通块节点为 k 个，有：g_n=\sum\limits_{k=1}^n\binom{n-1}{k-1}f_kg_{n-k}，于是我们得出了 f 与 g 的关系。

到了这一步，生成函数的作用就在于构建卷积关系，当然我们需要让函数的项只与次数相关。

将二项式拆开，得到 \dfrac{g_n}{(n-1)!}=\sum\limits_{k=1}^n\dfrac{f_k}{(k-1)!}\dfrac{g_{n-k}}{(n-k)!}，这就是一个卷积形式。

设 F=\sum\dfrac{f_i}{i!},G=\sum\dfrac{g_i}{i!}，分别是数列 f_i,g_i 的指数生成函数。

那么 xG'=xF'G,F=\int\dfrac{G'}G=\ln G，直接使用多项式对数函数即可。

Part4 另一个角度

上面只是用来发掘指数与计数的联系，其实普通生成函数也可以，甚至不用对数，毕竟对数的实现也是多项式求逆。

事实上，设 H=\sum\dfrac{g_i}{(i-1)!}x^i,F=\sum\dfrac{f_i}{(i-1)!}x^i,G=\sum\dfrac{g_i}{i!}x^i。

那么有 H=FG,F=\dfrac{H}G，多项式求逆即可。

Part5 后记

怎么会告一段落，生成函数远不只这些，当然可以放代码：

方法一：

int main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y;
    cin>>n;
    jc[0]=nv[0]=nv[1]=1;
    for(x=2;x<=n;++x)nv[x]=ll(M-M/x)*nv[M%x]%M;
    for(x=1;x<=n;++x){
        jc[x]=ll(jc[x-1])*x%M;
        nv[x]=ll(nv[x-1])*nv[x]%M;
    }
    for(x=0;x<=n;++x)g[x]=ll(qp(2,ll(x-1)*x/2%(M-1)))*nv[x]%M;
    P.Ln(g,f,18);
    k=ll(f[n])*jc[n]%M;
    printf("%d\n",k);
    return 0;
}

方法二：

int main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y;
    cin>>n;
    jc[0]=nv[0]=nv[1]=1;
    for(x=2;x<=n;++x)nv[x]=ll(M-M/x)*nv[M%x]%M;
    for(x=1;x<=n;++x){
        jc[x]=ll(jc[x-1])*x%M;
        nv[x]=ll(nv[x-1])*nv[x]%M;
    }
    for(x=0;x<=n;++x)g[x]=ll(qp(2,ll(x-1)*x/2%(M-1)))*nv[x]%M;
    P.Inv(g,f,18);
    memset(g,0,4<<19);
    for(x=1;x<=n;++x)g[x]=ll(qp(2,ll(x-1)*x/2%(M-1)))*nv[x-1]%M;
    P.mul(f,g);
    k=ll(f[n])*jc[n-1]%M;
    printf("%d\n",k);
    return 0;
}