zcmimi's blog

推荐:

定义

生成函数又称母函数

设序列aa_0,a_1,a_2,\dots

g(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots为序列a的生成函数

普通生成函数

普通型生成函数(ordinary generating function, 简称OGF)

形如\displaystyle G(x)=\sum_{i=0}^na_ix_i的表示一个序列的多项式函数,我们称之为普通生成函数

使用例

  1. 有1克、2克、3克、4克的砝码各一枚,能称出哪几种重量?每种重量各有几种可能方案?

    11克砝码可以看成1+x^1,1表示不取,x^n代表取n个,以下同理

    12克砝码可以看成1+x^2

    13克砝码可以看成1+x^3

    14克砝码可以看成1+x^4

    那么

    \begin{aligned} g(x) &=(1+x^1)(1+x^2)(1+x^3)(1+x^4)\\ &=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10} \end{aligned}

    可以看出重量为3克的方案为2种,4克的方案为2种,3克的方案为5种,以此类推

    可以发现得出的多项式每一项ax^n代表重量为n克的方案有a

    手动模拟一下多项式计算的过程,与背包dp相似,也可配合下发例题代码理解

  2. 求用1分、2分、3分的邮票贴出不同数值的方案数(邮票张数无限)

    那么

    \begin{aligned} g(x) &= \begin{aligned} &(1+x+x^2+x^3+\dots)\\ &(1+x^2+x^4+x^6+\dots)\\ &(1+x^3+x^6+x^9+\dots)\\ \end{aligned}\\ &=1+x+2x^2+3x^3+4x^4+\dots \end{aligned}

    x^4的系数为4表示44中拆分方法:

    4=1+1+1+1=1+1+1+2=1+3=2+2

  3. 设有n个标志为1,2,…,n的网袋,第i个网袋里放有n_i个球。不同网袋里的球是不同的,而同一网袋里的球则是没有差别的,认为是相同的。询问从中取r个球的方案数。

    g(x)=(1+x+x^2+\dots+x^{n_1})(1+x+x^2+\dots+x^{n_2})\dots

    最后指数为r的项的系数就是答案

例题

HDU 1028

给出n,求:

n=a_1+a_2+\dots+a_m(m\le n,a_i>0)的方案数

eg: n=4时有5种方案

\begin{aligned} &4=4\\ &4=3+1\\ &4=2+2\\ &4=2+1+1\\ &4=1+1+1+1\\ \end{aligned}

\begin{aligned} g(x)= &(1+x+x^2+x^3+\dots+x^n)\\ &(1+x^2+x^4+x^6+\dots+x^n)\\ &(1+x^3+x^6+x^9+\dots+x^n)\\ &\cdots\\ &(1+x^n)\\ \end{aligned}\\

#include<bits/stdc++.h>
int n,a[2][121];
int main(){
    for(int i=0;i<=120;++i)a[1][i]=1;
    for(int i=2;i<=120;++i){
        memset(a[i&1],0,sizeof a[i&1]);
        int p=0;
        for(int p=0;p<=120;p+=i)
            for(int j=0;j+p<=120;++j)
                a[i&1][j+p]+=a[!(i&1)][j];
                // ax^j · x^p = ax^{j+k}
                // a'[j+k]+=a[j]
    }
    while(~scanf("%d",&n))
        printf("%d\n",a[0][n]);
}

练习:

HDU 1085

推广

a=\{1,1,1,\dots\}时,g(x)=1+x+x^2+x^3+\dots

x\in(-1,1)时:

\displaystyle g(x)=1+x+x^2+x^3+\dots+x^{n-1} \\ xg(x)=x+x^2+x^3+x^4+\dots+x^n \\ g(x)=\frac{xg(x)-g(x)}{x-1}=\frac{x^n-1}{x-1} \\ \because x\in(-1,1),n=\infty \\ \therefore x^n \rightarrow 0 \\ \therefore g(x)=\frac1{1-x}

所以:

\displaystyle \frac1{1-x}=1+x+x^2+x^3+\dots

x替换为kx:

\displaystyle \frac 1{1-kx}=1+kx+k^2x^2+k^3x^3+\dots

两边分别求导得:

\displaystyle \frac1{(1-x)^2}=0+1+2x+3x^2+4x^3+\dots

再求导:

\displaystyle \frac2{(1-x)^3}=0+0+1+3x+6x^2+10x^3+\dots

推广: \displaystyle \sum_{i=0}^\infty {i+k-1 \choose k-1}x^i=\frac1{(1-x)^k}

常见生成函数:

数列 OGF
<1,0,0,\dots> 1
<1,1,1,\dots> \frac 1{1-x}
<1,k,k^2,k^3,\dots> \frac 1{1-kx}
<1,2,3,\dots> \frac 1{(1-x)^2}
<1,−1,1,−1,\dots> \frac 1{1+x}
<1,2,1,0,0,\dots> (1+x)^2
<1,4,6,4,1,0,0,\dots> (1+x)^4
<1,n,{n\choose 2},{n\choose 3},\dots> (1+x)^n
<1,n,{n+1\choose 2},{n+1\choose 3},\dots> (1-x)^{-n}
<0,1,\frac 12,\frac 13,\dots> ln(1-x)
<0,1,-\frac 12,\frac 13,-\frac 14,\dots> ln(1+x)
<1,1,\frac 12,\frac 1{3!},\frac 1{4!},\dots> e^x

板子题

LG 2000 拯救世界

  1. 金神石的块数必须是6的倍数 g(x)=1+x^6+x^{12}+...=\frac 1{1-x^6}
  2. 木神石最多用9块 g(x)=1+x+x^2+...+x^9=\frac{1-x^{10}}{1-x}
  3. 水神石最多用5块 g(x)=1+x+x^2+...+x^5=\frac{1-x^6}{1-x}
  4. 火神石的块数必须是4的倍数 g(x)=1+x^4+x^8+...=\frac 1{1-x^4}
  5. 土神石最多用7块 g(x)=1+x+x^2+...+x^7=\frac{1-x^8}{1-x}

  6. 金神石的块数必须是2的倍数 g(x)=1+x^2+x^4+...=\frac 1{1-x^2}

  7. 木神石最多用1块 g(x)=1+x=\frac{1-x^2}{1-x}
  8. 水神石的块数必须是8的倍数 g(x)=1+x^8+x^{16}+...=\frac 1{1-x^8}
  9. 火神石的块数必须是10的倍数 g(x)=1+x^{10}+x^{20}+...=\frac 1{1-x^{10}}
  10. 土神石最多用3块 g(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}

\displaystyle \frac 1{1-x^6}\cdot\frac{1-x^{10}}{1-x}\cdot\frac{1-x^6}{1-x}\cdot\frac 1{1-x^4}\cdot\frac{1-x^8}{1-x}\cdot\frac 1{1-x^2}\cdot\frac{1-x^2}{1-x}\cdot\frac 1{1-x^8}\cdot\frac 1{1-x^{10}}\cdot\frac{1-x^4}{1-x}\\ =\frac1{(1-x)^5}\\ =\sum_{i=0}^\infty {i+4 \choose 4}x^i

n项的系数是{n+4 \choose 4}需要FFT或NTT

求斐波那契数列通项公式

斐波那契数列:

f_0=1,f_1=1,f_i=f_{i-1}+f_{i-2}(i>1)

构造生成函数:

F(x)=x+x^2+2x^3+3x^4+5x^5+\dots

构造方程:

\begin{aligned} &\quad F(x)-xF(x)\\ &=(x+x^2+2x^3+3x^4+\dots)-(x^2+x^3+2x^4+3x^5+\dots)\\ &=x+x^3+x^4+2x^5+3x^6+\dots\\ &=x+x^2F(x) \end{aligned}

解得:

F(x)=\frac x{1-x-x^2}

配方:

F(x)=\frac x{(1-\phi_1 x)(1-\phi_2 x)} \\~\\ \displaystyle \phi_1=\frac{1+\sqrt 5}2,\phi_2=\frac{1-\sqrt 5}2

裂项:

F(x)=\frac 1{\sqrt 5}\left( \frac 1{1-\phi_1x} - \frac 1{1-\phi_2x} \right)

那么:

f_n=\frac 1{\sqrt 5}\left[ \left( \frac{1+\sqrt 5}2 \right)^n - \left( \frac{1-\sqrt 5}2 \right)^n \right]

指数型生成函数

定义

指数型生成函数(exponential generating function,简称EGF)

形如\displaystyle G(x)=\sum_{i=0}^n a_i \frac{x^i}{i!}的表示序列的多项式函数,我们称之为指数型生成函数

使用例

有三种物品,分别有3,2,3个,问拿出4个进行排列(不同顺序算不同方案)的方案数是多少

多重集排列数:

S={a_1,a_2,\dots,a_n},N=\sum\limits_{i=1}^n a_i,其中a_i表示第i个物品有a_i个。 从中选出N个进行排列的方案数为\displaystyle \frac{N!}{a_1! a_2! \dots a_n!} 解释: 任意排列之后减去同种物品之间多出来的方案

构造:

\displaystyle G_1(x)=1+\frac x{1!}+\frac {x^2}{2!}+\frac {x^3}{3!}\\~\\ G_2(x)=1+\frac x{1!}+\frac {x^2}{2!}\\~\\ G_3(x)=1+\frac x{1!}+\frac {x^2}{2!}+\frac {x^3}{3!}\\

那么

\begin{aligned} &\quad G_1(x)\cdot G_2(x) \cdot G_3(x)\\ &=(1+\frac x{1!}+\frac {x^2}{2!}+\frac {x^3}{3!})(1+\frac x{1!}+\frac {x^2}{2!})(1+\frac x{1!}+\frac {x^2}{2!}+\frac {x^3}{3!})\\ &=(1+3x + \frac{9}{2}x^2 + \frac{14}{3}x^3 + \frac{35}{12}x^4 + \frac{17}{12}x^5 + \frac{35}{72} x^6 + \frac{8}{72}x^7 + \frac{1}{71}x^8) \end{aligned}

4个物品的方案数就是4!\cdot \frac{35}{12}=70

hdu 1521 排列组合

#include<bits/stdc++.h>
const int N=11;
int n,m,a[N],fac[100000],mx=0;
typedef double db;
db c[2][N];
void solve(){
    mx=m;
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        if(a[i]>mx)mx=a[i];
    }
    fac[0]=1;
    for(int i=1;i<=mx;++i)fac[i]=fac[i-1]*i;
    memset(c,0,sizeof c);
    for(int i=0;i<=a[1];++i)
        c[1][i]=1.0/(db)fac[i];
    for(int i=2;i<=n;++i){
        memset(c[i&1],0,sizeof c[i&1]);
        for(int p=0;p<=m;++p)
            for(int j=0;j<=a[i]&&j+p<=m;++j)
                c[i&1][j+p]+=c[!(i&1)][p]/(db)fac[j];
    }
    printf("%.0f\n",c[n&1][m]*fac[m]);
}
int main(){
    while(~scanf("%d%d",&n,&m))solve();
}

推广

\displaystyle e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!}

常见的指数型生成函数:

数列 EGF
<1,1,1,\dots> e^x
<1,-1,1,-1,\dots> e^{-x}
<1,k,k^2,k^3,\dots> e^{kx}
<0,1,2,\dots> xe^x
<1,0,1,0,\dots> \frac {e^x+e^{-x}}2
<0,1,0,1,\dots> \frac {e^x-e^{-x}}2

可以发现<f_n>的EGF就是<\frac{f_n}{n!}>的OGF

例题:

poj 3734 积木

长度为n的序列,用红黄蓝绿染色,其中红、绿数量均为偶数,求方案数

红、绿: \frac{e^x+e^{-x}}2

黄、蓝: e^x

\displaystyle \begin{aligned} F(x) &=e^x \cdot \frac{e^x+e^{-x}}2 \cdot e^x \cdot \frac{e^x+e^{-x}}2\\ &=\left(e^x \cdot \frac{e^x+e^{-x}}2\right)^2\\ &=\left(\frac{e^{2x}+1}2\right)^2\\ &=\frac{e^{4x}+2e^{2x}+1}4\\ &=\frac 14+\sum_{i=0}^{\infty} \frac{4^i+2^{i+1}}4 \cdot \frac{x^i}{n!} \end{aligned} \\ f_n=\frac{4^n+2^{n+1}}4

#include<cstdio>
typedef long long ll;
const int P=10007;
int n;
int pw(ll x,int b){
    ll res=1;
    while(b){
        if(b&1)res=res*x%P;
        x=x*x%P;b>>=1;
    }
    return res;
}
int main(){
    int T;scanf("%d",&T);
    while(T--)
        scanf("%d",&n),
        printf("%d\n",(pw(4,n)+pw(2,n+1))%P*2502%P);
}
生成函数
comment评论
Search
search