【算法与数据结构】——母函数及其应用

╰半橙微兮° 2023-01-17 09:28 114阅读 0赞

# 母函数定义 #

对于序列a0,a1,a2,·····构造一函数: G ( x ) = a 0 + a 1 x + a 2 x 2 + G(x)=a\_0+a\_1x+a\_2x^2+ G(x)=a0\+a1x\+a2x2\+···，称函数G(x)是序列 a 0 , a 1 , a 2 a\_0,a\_1,a\_2 a0,a1,a2···的母函数

## 例1 ##

问题:若有1克,2克,3克,4克的砝码各一枚,能称出哪几种重量?各有集中可能方案?  
构造母函数,用x的指数表示称出的重量,则:  
![在这里插入图片描述][20210428204821585.png]  
砝码称重的组合情况,用以上几个函数的乘积表示:  
得: 1 + x + x 2 + 2 x 3 + 2 x 4 + 2 x 5 + 2 x 6 + 2 x 7 + x 8 + x 9 + x 10 1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^\{10\} 1\+x\+x2\+2x3\+2x4\+2x5\+2x6\+2x7\+x8\+x9\+x10  
指数即能称出的重量,对应的系数即称出此重量的方法数

## 例2(可重复) ##

求用1分2分3分的邮票贴出不同数值的方案数(邮票可重复)  
母函数为:  
 G ( x ) = ( 1 + x + x 2 + x 3 + ⋅ ⋅ ⋅ ) ( 1 + x 2 + x 4 + ⋅ ⋅ ⋅ ) ( 1 + x 3 + x 6 + ⋅ ⋅ ⋅ ) G(x)=(1+x+x^2+x^3+···)(1+x^2+x^4+···)(1+x^3+x^6+···) G(x)=(1\+x\+x2\+x3\+⋅⋅⋅)(1\+x2\+x4\+⋅⋅⋅)(1\+x3\+x6\+⋅⋅⋅)

## 普通母函数模板 ##

#include<stdio.h>
    #include<stdlib.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;
    )

# 指数型母函数 #

定义:对于序列 a 0 , a 1 , a 2 , ⋅ ⋅ ⋅ a\_0,a\_1,a\_2,··· a0,a1,a2,⋅⋅⋅函数 G ( x ) = a 0 + a 1 / 1 ! ⋅ x + a 2 / 2 ! ⋅ x 2 + a 3 / 3 ! ⋅ x 3 + ⋅ ⋅ ⋅ + a k / k ! ⋅ x k + ⋅ ⋅ ⋅ G(x)=a\_0+a\_1/1!·x+a\_2/2!·x^2+a\_3/3!·x^3+···+a\_k/k!·x\_k+··· G(x)=a0\+a1/1!⋅x\+a2/2!⋅x2\+a3/3!⋅x3\+⋅⋅⋅\+ak/k!⋅xk\+⋅⋅⋅称为序列 a 0 , a 1 , a 2 , ⋅ ⋅ ⋅ a\_0,a\_1,a\_2,··· a0,a1,a2,⋅⋅⋅对应的指数型母函数。  
这样，对于一个多重集，其中 a 1 a\_1 a1重复 n 1 n\_1 n1次, a 2 a\_2 a2重复 n 2 n\_2 n2次,···, a k a\_k ak重复 n k n\_k nk次,从中取r个排列的不容排列数所对应的指数型母函数为:  
![在这里插入图片描述][20210429152030147.png]

## 指数型母函数-参考代码 ##

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;
    )

[20210428204821585.png]: /images/20221021/c736e90534c9442fb317e705d8cfb4f5.png
[20210429152030147.png]: /images/20221021/2315974b7a364a7092bacf7830676b38.png