母函数模板

#include <stdio.h>
#define MAX 10000
int c1[MAX], c2[MAX];
// c1是保存各项质量砝码可以组合的数目
// c2是中间量，保存每一次的情况
// 每个n的种类无限
// (1 + x^1 + x^2 + ...+ x^n)(1 + x^2 + x^4 +....+x^n)(1 + x^3 +...+ x^n)....(1 + x^n)
int main()
{
	int n;
	while( scanf("%d", &n)!=EOF)
	{
		for(int i=0; i<=n; i++)						//第一项全部至0
		{
			c1[i]=1;	c2[i]=0;
		}
		for(int i=2; i<=n; i++)
		{
			for(int j=0; j<=n; j++)
				for(int k=0; k+j<=n; k+=i)
					c2[k+j] += c1[j];				//一定得是累加
			
			for(int j=0; j<=n; j++)					//结束一轮运算赋值
			{
				c1[j] = c2[j];	c2[j] = 0;
			}
		}
		printf("%d\n", c1[n]);
	}
	return 0;
}

附件列表