母函数入门

ゝ一纸荒年。 2022-06-09 10:47 169阅读 0赞

母函数也叫生成函数，是组合数学中尤其是计数方面的一个重要理论和工具。母函数有普通型母函数和指数型母函数两种，其中普通型用的比较多。形式上说，普通型母函数用于解决多重集的组合问题，而指数型母函数用于解决多重集的排列问题。母函数还可以解决递归数列的通项问题（例如使用母函数解决斐波那契数列的通项公式）。

**定义：**

![Center][]

![Center 1][]

在这里给出几个网站供大家学习母函数

递归与母函数：

https://wenku.baidu.com/view/c0f7ee05cc1755270722080d.html

母函数题目小结：

http://blog.csdn.net/ACM\_cxlove/article/details/7831070

母函数详解与模板：

http://blog.csdn.net/xiaofei\_it/article/details/17042651

普通型母函数模板：

int Num;//因子个数
    int n1[MAXN];//n1[i]表示该乘积表达式第i个因子的起始系数
    int n2[MAXN];//n2[i]表示该乘积表达式第i个因子的终止系数
    int v[MAXN];//v[i]表示该乘积表达式第i个因子的权重
    int P;//P是可能的最大指数
    int a[MAXN], b[MAXN];//a为计算结果，b为中间结果。 
    
    void solve()
    {
    	memset(a, 0, sizeof(a));
    	a[0] = 1;
    	for (int i = 1; i <= Num; i++)//循环每个因子  
    	{
    		memset(b, 0, sizeof(b));
    		for (int j = n1[i]; j <= n2[i] && j*v[i] <= P; j++)//循环每个因子的每一项  
    			for (int k = 0; k + j*v[i] <= P; k++)//循环a的每个项  
    				b[k + j*v[i]] += a[k];//把结果加到对应位  
    		memcpy(a, b, sizeof(b));//b赋值给a  
    	}
    }

普通型母函数优化模板(引入last变量)：

int Num;//因子个数
    int n1[MAXN];//n1[i]表示该乘积表达式第i个因子的起始系数
    int n2[MAXN];//n2[i]表示该乘积表达式第i个因子的终止系数
    int v[MAXN];//v[i]表示该乘积表达式第i个因子的权重
    int P;//P是可能的最大指数
    int a[MAXN], b[MAXN];//a为计算结果，b为中间结果。
    int last;//最大的指数位置
    
    void solve()
    {
    	//初始化a，因为有last，所以这里无需初始化其他位  
    	a[0] = 1;
    	last = 0;
    	for (int i = 1; i<=Num; i++)
    	{
    		int last2 = min(last + n2[i] * v[i], P);//计算下一次的last  
    		memset(b, 0, sizeof(int)*(last2 + 1));//只清空b[0..last2]  
    		for (int j = n1[i]; j <= n2[i] && j*v[i] <= last2; j++)//这里是last2  
    			for (int k = 0; k <= last&&k + j*v[i] <= last2; k++)//这里一个是last，一个是last2  
    				b[k + j*v[i]] += a[k];
    		memcpy(a, b, sizeof(int)*(last2 + 1));//b赋值给a，只赋值0..last2  
    		last = last2;//更新last  
    	}
    }

指数型母函数模板

int Num;//物品个数   
    int v[MAXN];//v[i]表示第i个物品可以选的个数  
    int P;//P是要选的物品总数 
    double a[MAXN], b[MAXN];//a为计算结果，b为中间结果。  
    double c[MAXN];
    
    void Factorial()
    {
    	c[0] = 1;
    	c[1] = 1;
    	for (int i = 2; i <= 20; i++)
    		c[i] = c[i - 1] * i;
    }
    
    void solve()
    {
    	int i, j, k;
    	Factorial();
    	memset(a, 0, sizeof(a));
    	memset(b, 0, sizeof(b));
    	for (i = 0; i <= v[1]; ++i)
    		a[i] = 1.0 / c[i];
    	for (i = 2; i <= Num; i++)
    	{
    		for (j = 0; j <= P; ++j)
    			for (k = 0; k + j <= P && k <= v[i]; ++k)
    				b[j + k] += a[j] / c[k];
    		for (j = 0; j <= P; ++j)
    		{
    			a[j] = b[j];
    			b[j] = 0;
    		}
    	}
    }答案为a[P]*c[P]

[Center]: /images/20220609/f8a38219e7cf459286a05fe3ef72ec34.png
[Center 1]: /images/20220609/83abd1a31fd34fdb963bd95800ea6ecd.png