## 母函数及其应用



 普通母型函数

研究以下多项式乘法:

$(1+a_1x)(1+a_2x)...(1+a_nx) \\ =1+(a_1+a_2+...+a_n)x +(a_1a_2+a_1a_3+...+a_{n-1}a_{n})x^2+ \\ ...+a1a2..a_nx^n$

 $对于序列a0,a1,a2..构造函数: \\ G(x)=a_0+a_1x+a_2x^2+...$

称G(x)是序列a0,a1,a2...的母函数

母函数是一种 **把组合问题转化为多项式乘法问题** 的方法。

**核心思路**：

- 多项式的 **指数** 表示某种“数值”（如重量、金额、个数）
- 多项式的 **系数** 表示达到该数值的“方案数”
- 多个问题的组合 = 对应多项式的 **乘法问题**

如果已知函数G(X)=(1+x)^2,我们也可以生成一个序列1,2,1，所以：

G(X)=(1+X)^2是1，2，1的母函数



如果已知G(X)=(1+x)^n,对应的生成序列？

若有1g、2g、3g、4g的砝码各一枚，若要称出6g，称重的方案是?

能称出几种重量？各有几种可能方案？

构造母函数，用x的指数表示称出的重量：

1个1g的砝码用1+x表示

1个2g的砝码用1+x^2表示

1个3g的砝码用1+x^3表示

1个4g的砝码用1+x^4表示



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

$(1+x)(1+x^2)(1+x^3)(1+x^4) $

为什么要带上1呢？1相当于没有这类砝码





求用1分、2分、3分邮票贴出不同数值的方案数——因允许重复，故母函数

$G(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)$

 

若有1克砝码3枚，2克砝码4枚，4克砝码2枚，问能称出哪几种重量？各有几种方案？

$G(x)=(1+x+x^2+x^3)(1+x^2+x^4+x^6+x^8)(1+x^4+x^8)$

整数拆分问题

整数n拆分成1，2，3...，m的和，求母函数

若上例m至少出现一次，其母函数又如何？

算f(n-m)

编码的时候就可以去掉1，表示至少用了一次m



关键：对多项式展开



矩阵连乘问题，合并两个括号，把原来20个问题缩小成19个问题

三个循环搞定

$G(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)$

```
#include <bits/stdc++.h>
using namespace std;
const int lmax=10000;
int c1[lmax+l],c2[lmax+l];
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;//表示当前已乘完的括号的结果多项式中x^i的系数,第一个括号
核心循环：依次乘上第2个到第n个括号
for (i=2;i<=n;i++)
{
for(j=0:j<=n;j++)
/*
i：当前正在乘第 i 个括号

j：遍历 c1 中已有的指数（当前已乘结果中 x^j 的系数），控制第一个括号

k：遍历当前括号的指数，每次增加 i（k = 0, i, 2i, ...），控制第二个括号

x^j x x^k=x^(j+k)
*/
	{
	for (k=0;k+j<=n;k+=i)
	{ 
	c2[j+k]+=c1[j]*1;}//c2临时数组，存放当前正在乘的下一个新括号的中间结果，相乘后的结果
	}


	for (j=0:j<=n:j++)// 更新c1，清空c2
	{ c1[j]=c2[j];
	c2[j]=0;
	}
	}
	
cout<<c1[n]<<endl;}
return 0;
}
```

$(\Sigma_j c1[j]x^j) \times (\Sigma_k x^{ki})=\Sigma_{j,k} c1[j]x^{j+ki}$

$1^2,2^2,3^2...,17^2$17种币值

Sample Input

2   //要凑成的面值

10

30

0

Sample output

1

4

27

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


int main(){
int n,i,j,k;
int elem[17]={1,4,...,289};
while (cin>>n && n!=0)
{
for (i=0;i<=n;i++)
{c2[i]=0;c1[i]=1;}
for (i=2;i<=17;i++)
{for (j=0;j<=n;j++)
for (k=0;k+j<=n;k+=elem[i-1])//按i^2增长
{c2[j+k]+=c1[j];}
for (j=0;j<=n;j++)
{c1[j]=c2[j]; c2[j]=0;}
}
cout<<cl[n]<<endl;
}
return 0;}
}

```



1分、2分、5分

不能支付的最小值是多少？

求方案（系数）是0的

[Problem - 1171](https://acm.hdu.edu.cn/showproblem.php?pid=1171)

**输入**
输入包含多个测试用例。每个测试用例以一个整数N开头（0 < N ≤ 50 —— 不同设施的种类数）。
接下来的N行，每行包含两个整数：V（0 < V ≤ 50 —— 设施的价值）和 M（0 < M ≤ 100 —— 该种设施的数量）。
你可以假设所有的V值都是不同的。
以负整数开头的测试用例表示输入结束，该测试用例不予处理。



**输出**
对于每个测试用例，输出一行，包含两个整数A和B，分别表示计算机学院和软件学院分得的设施总价值。
A和B应尽可能相等，同时保证A不小于B。

母函数思路

母函数:

$G(x)=\Pi_{i=1}^N(1+x^{V_i}+...x^{M_iV_i})$

展开后，x^k的系数表示能否选出总价值为 k*k* 的子集（系数非零即可，因为这里不统计方案数，只需知道可行性）。



总价值的一半方案有没有

1. 计算总价值 S。
2. 从 S/2 向下找第一个系数非零的指数 B。
3. A=S−B，保证 A≥B。



```Cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXV = 50;          // 每种价值 ≤50
const int MAXM = 100;         // 每种数量 ≤100
const int MAXN = 50;          // 种类数 ≤50
const int MAXSUM = MAXV * MAXM * MAXN; // 最大总和 ≤ 250000

int c1[MAXSUM + 5], c2[MAXSUM + 5];
int val[55], num[55];

int main() {
    int N;
    while (cin >> N && N >= 0) {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            cin >> val[i] >> num[i];
            sum += val[i] * num[i];
        }

        // 初始化母函数：c1[k] 表示能否组成价值 k
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));

        // 第一个物品的初始化
        for (int k = 0; k <= num[0]; k++) {
            c1[k * val[0]] = 1;
        }

        // 依次乘上后面每个物品
        for (int i = 1; i < N; i++) {
            for (int j = 0; j <= sum; j++) {
                if (c1[j]) {
                    for (int k = 0; k <= num[i] && j + k * val[i] <= sum; k++) {
                        c2[j + k * val[i]] = 1;
                    }
                }
            }
            // 把 c2 赋给 c1，清空 c2
            for (int j = 0; j <= sum; j++) {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }

        // 从 sum/2 向下找第一个可组成的价值
        int half = sum / 2;
        int B = half;
        while (B >= 0 && !c1[B]) B--;
        int A = sum - B;

        cout << A << " " << B << endl;
    }
    return 0;
}
```

一、母函数与背包问题的对应关系

| 母函数概念               | 背包问题概念                     |
| :----------------------- | :------------------------------- |
| 多项式$1+x^w$            | 一个重量为 w 的物品（取或不取）  |
| 多项式$1+x^w+..1+x^{mw}$ | m 个重量为 w 的物品（取 0~m 个） |
| 多项式乘法               | 状态转移（叠加方案）             |
| $x^k$的系数              | 凑出重量 k 的方案数/可行性       |
| 指数 k                   | 背包容量/总重量                  |





母函数对应的是可求方案数/ 可行性

0-1背包



关于称重问题，在1和砝码总重量之间，有哪一些重量称不出来？

砝码可以两边都放

```
for (k=0;k+j<=n;k+=elem[i-1])//按i^2增长
{c2[j-|k|]+=c1[j];}(j和k既可以j+k又可以j-k)
```



思考和总结很重要