【hdoj_2189】来生一起走(母函数)

题目：http://acm.hdu.edu.cn/showPRoblem.php?pid=2189

本题的数学模型如下：

分解的问题，常用母函数求解，这里要求每个“硬币”的价值必须为素数，所以需要写一个函数判断一个数是否位素数.

然后再套用母函数模板：

http://blog.csdn.net/ten_sory/article/details/59483762

C++代码如下：

#include<iostream>using namespace std;int IsPrime(int n){	for(int i=2;i<=n-1;i++)		if(n%i==0)			return 0;	return 1;}int main(){	int C;	cin >> C;	while(C--)	{		int i,j,m;		int n;		cin >> n;		int k = n-1;		int *v = new int[k+1];		int s = 0;		int e = 100;			for(i=1;i<=k;i++)			v[i] = i+1;		//注意此处模板中的MAX = n;所以下面定义数组要用n+1的长度去定义.		int *a = new int[n+1];		int *b = new int[n+1];		for(i=0;i<=n;i++)		{			a[i] = 0;			b[i] = 0;		}		a[0] = 1;		for(i=1;i<=k;i++)//一共n-1个()相乘，硬币数量分别是2~n，下面要除去其中不是素数的情况		{			if(IsPrime(v[i]))//如果硬币数量是素数，才可以			{				for(j=s;j<=e && j*v[i]<=n;j++)					for(m=0;m+j*v[i]<=n;m++)						b[m+j*v[i]]+=a[m];				for(m=0;m<=n;m++)				{					a[m] = b[m];					b[m] = 0;				}				}		}		cout << a[n] << endl;	}	return 0;}上述代码，提交可以通过.