母函数

发表于 2023-01-14 更新于 2025-07-26 分类于程序设计竞赛

母函数

定义

使用幂次作为变量 幂次乘法是指数相加

砝码称重的组合情况，可以用以上几个函数的乘积表示：

\((1+x)(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}\)

例题二

求用1分、2分、3分的邮票贴出不同数值的方案数——因邮票允许重复，故母函数为： \[ G(x) = (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \cdot (1 + x^3 + x^6 + \dots) \]

例题三

概念：整数拆分，就是把整数分解成若干整数的和，比如：\(3 = 1+1+1\)，\(3 = 1+2\) 等等；
整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。
练习： 整数\(n\)拆分成\(1\)，\(2\)，\(3\)，\(\cdots\)，\(m\)的和，求母函数。

公式： (1 + x + x² + x³ + …) * (1 + x² + x⁴ + …) * …
若要求“1必须用一次”，则修改为： (x + x² + x³ + …) * (1 + x² + x⁴ + …) * …

计算母函数：

普通型母函数-模板（整数拆分为例）

#include <bits/stdc++.h>
using namespace std;
const int lmax = 10000;
int c1[lmax + 1], c2[lmax + 1];
int main()
{
    int n, i, j, k;
    while (cin >> n)
    {
        for (i = 0; i <= n; i++)
        {
            c1[i] = 0;
            c2[i] = 0;
        }
        for (i = 0; i <= n; i++)
            c1[i] = 1;
        for (i = 2; i <= n; i++)
        {
            for (j = 0; j <= n; j++)
                for (k = 0; k + j <= n; k += i)
                {
                    c2[j + k] += c1[j];
                }
            for (j = 0; j <= n; j++)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        cout << c1[n] << endl;
    }
    return 0;
}

例题改编 k+=i^2

#include <iostream>
using namespace std;
const int lmax=300;
int cl[lmax+1],c2[lmax+1];
int main()
{
    int n,i,j,k;
    while (cin>>n && n!=0)
    {
        for (i=0;i<=n;i++)
        {
            cl[i]=1;    c2[i]=0;
        }
        for (i=2;i<=17;i++)
        {
            for (j=0;j<=n;j++)
                for (k=0;k+j<=n;k+=i*i)
                {
                    c2[j+k]+=cl[j];
                }
            for (j=0;j<=n;j++)
            {
                cl[j]=c2[j]; c2[j]=0;
            }
        }
        cout<<cl[n]<<endl;
    }
    return 0;
}

或做一些变化

//变化一点，灵活很多
int main(void)
{
    int n,i,j,k;
    int elem[17]={1,4,9,16,25,36,...,169,196,225,256,289};
    while (cin>>n && n!=0)
    {
        for (i=0;i<=n;i++)
        {
            c1[i]=1;    c2[i]=0;
        }
        for (i=2; i<=17; i++)
        {
            for (j=0;j<=n;j++)
            {
                for (k=0;k+j<=n; k+=elem[i-1] )
                {
                    c2[j+k]+=c1[j];
                }
            }
            for (j=0;j<=n;j++)
            {
                c1[j]=c2[j];    c2[j]=0;
            }
        }
        cout<<c1[n]<<endl;
    }
    return 0;
}

例题1,2,5 求系数为0的 例题天平称重 k+j 和 k-j 都可以称量出来

指数级母函数：（解决选数排列问题）

考虑n个元素组成的多重集，其中\(a_1\)重复了\(n_1\)次，\(a_2\)重复了\(n_2\)次，…，\(a_k\)重复了\(n_k\)次，\(n = n_1 + n_2 + \cdots + n_k\)。
现在从中取r个进行排列，求不同的排列数。
若\(r = n\)，即考虑n个元素的全排列，则不同的排列数显然是： \[\frac{n!}{n_1!n_2!\cdots n_k!}\]

先看一个具体的问题：假设有8个元素，其中\(a_1\)重复3次，\(a_2\)重复2次，\(a_3\)重复3次。

从中取\(r\)个组合，其组合数为\(c_r\)，则其对应的母函数为： \[ G(x) = (1 + x + x^2 + x^3)(1 + x + x^2)(1 + x + x^2 + x^3) \] \[ = (1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5)\ (1 + x + x^2 + x^3) \] \[ = 1 + 3x + 6x^2 + 9x^3 + 10x^4 + 9x^5 + 6x^6 + 3x^7 + x^8 \]

从\(x^4\)的系数可知，从这8个元素中取4个组合，不同的组合数为10。

样例

为了便于计算，形式地引进函数：

\[ \begin{align*} G_e(x) &= \left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!}\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}\right) \\\\ &= 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}{72}x^8 \\\\ &= 1 + \frac{3}{1!}x + \frac{9}{2!}x^2 + \frac{28}{3!}x^3 + \frac{70}{4!}x^4 + \frac{170}{5!}x^5 + \frac{350}{6!}x^6 + \frac{560}{7!}x^7 + \frac{560}{8!}x^8 \end{align*} \]

定义

定义：对于序列 \(a_0, a_1, a_2, \cdots\)，函数 \[ G_e(x) = a_0 + \frac{a_1}{1!}x + \frac{a_2}{2!}x^2 + \frac{a_3}{3!}x^3 + \cdots + \frac{a_k}{k!}x^k + \cdots \]

称为序列\(a_0, a_1, a_2, \cdots\)对应的指数型母函数。

这样，对于一个多重集，其中 \(a_1\) 重复\(n_1\)次，\(a_2\)重复\(n_2\)次，\(\cdots\)，\(a_k\)重复\(n_k\)次，从中取 r 个排列的不同排列数所对应的指数型母函数为： \[ G_e(x) = \left( 1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots + \frac{x^{n_1}}{n_1!} \right) \left( 1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots + \frac{x^{n_2}}{n_2!} \right) \cdots \left( 1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots + \frac{x^{n_k}}{n_k!} \right) \]

例题1

有n种物品，已知每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有”AB”,“BA”两种。

每组输入数据有两行，第一行是二个数n,m(1<=m,n<=10)，含义如上。第二行有n个数，分别表示这n件物品的数量。

对应每组数据，请输出所有可能的排列数。

解决：构造指数型母函数

题目分析：
本题已知每种物品的数量，求的是排列数
结论：典型的指数型母函数的应用
对应的母函数：

\[ G_{e}(x)=\left(1+\frac{x}{1!}+\frac{x^{2}}{2!}+\cdots+\frac{x^{n_{1}}}{n_{1}!}\right)\left(1+\frac{x}{1!}+\frac{x^{2}}{2!}+\cdots+\frac{x^{n_{2}}}{n_{2}!}\right)\cdots\left(1+\frac{x}{1!}+\frac{x^{2}}{2!}+\cdots+\frac{x^{n_{k}}}{n_{k}!}\right) \]

代码

const int N = 21;
double c1[N], c2[N]; // 注意类型
int val[N], F[N];
void Factorial()
{ 
    F[0]=1;             //注意初始化
    for(int i = 1; i <=20; i++){
        F[i]=F[i-1]*i;
    }
}
int main()
{ 
    int n, m, i, j, k;
    Factorial();       //预处理
    while(~scanf("%d%d", &n, &m)){
        for(i = 0; i < n; ++ i){
            scanf("%d", &val[i]);
        }
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        for(i=0; i <= val[0]; ++i){
            c1[i] = 1.0/F[i];
        }
        for(i=1; i<n; i++){
            for(j = 0; j <= m; ++j){
                for(k = 0; k+j<=m && k<=val[i]; ++k){
                    c2[j + k] += c1[j]/F[k];
                }
            }
            for(j = 0; j <= m; ++j){
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        printf("%.0f\n", c1[m]*F[m]);
    }
    return 0;
}

例题2

现在有一长度为N的字符串，满足以下条件：

字符串仅由A,B,C,D四个字母组成；
A出现偶数次（也可以不出现）；
C出现偶数次（也可以不出现）；

比如：当N=2时，所有满足条件的字符串有如下6个：BB,BD,DB,DD,AA,CC。

请计算满足条件的字符串个数，由于数据非常大，给出最后两位数字即可。

每组输入的第一行是一个整数T，表示测试实例的个数，下面是T行数据，每行一个整数N（1<=N<2^64），当T=0时结束。

母函数 +矩阵快速幂：

题目分析：

首先，你能想到什么算法？

求A B C D在规定条件下N个元素的排列个数，这个题目也可以用指数型母函数来解决，对应的指数型母函数：

\[ G(X)=(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots)^2 * (1+\frac{x^2}{2!}+\frac{x^4}{4!}+\dots)^2 \]

前者表示：B,D出现方式不限制；

后者表示：A,C只能出现偶数或者不出现情况；

题目难点：本题的数据规模特点？

\[ (1 <= N < 2^{64}) \]

需要用到化简公式代入

指数型母函数的公式化简：

关键泰勒展开式： \[ \begin{align*} \mathrm{e}^x &= 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots, \\\\ \mathrm{e}^{-x} &= 1 - \frac{x}{1!} + \frac{x^2}{2!} - \frac{x^3}{3!} + \cdots. \end{align*} \]

化简过程： \[ \begin{align*} G(x) &= \mathrm{e}^{2x} \cdot \left( \frac{\mathrm{e}^x + \mathrm{e}^{-x}}{2} \right)^2 \\\\ &= \frac{1}{4} \cdot \mathrm{e}^{2x} \cdot \left( \mathrm{e}^{2x} + 2 + \mathrm{e}^{-2x} \right) \\\\ &= \frac{1}{4} \left( \mathrm{e}^{4x} + 2\mathrm{e}^{2x} + 1 \right) \\\\ &= \frac{1}{4} \Bigg[ \left( 1 + \frac{4x}{1!} + \frac{(4x)^2}{2!} + \cdots + \frac{(4x)^n}{n!} + \cdots \right) \\\\ &\quad + 2 \left( 1 + \frac{2x}{1!} + \frac{(2x)^2}{2!} + \cdots + \frac{(2x)^n}{n!} + \cdots \right) + 1 \Bigg] \end{align*} \]

提取 \(x^n\) 项： \[ \begin{align*} \frac{x^n}{n!} \text{的系数} &= \frac{1}{4} \left( \frac{4^n x^n}{n!} + 2 \cdot \frac{2^n x^n}{n!} \right) \\\\ &= \frac{1}{4} \left( \frac{4^n + 2^{n+1}}{n!} \right) x^n \\\\ &= \left( 4^{n-1} + 2^{n-1} \right) \frac{x^n}{n!} \end{align*} \]

最终所求方案数为： \[ \boxed{ \left( 4^{n-1} + 2^{n-1} \right) \bmod 100 } \]

接下来快速幂处理方案数