mumfunction.cpp

ACM程序竞赛中会有不少题目会用到母函数的技巧

#include <iostream>
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)/*循环变量k作为下标 
			 表示的是指数，c2[j+k],c1[j]中的值是系数。
			 而这里为什么每循环一次k要加i呢？
			 k每次的变化遵循的是什么规律呢？
			 他的规律是，每次乘的第i次的时候，每第i大项
			 中的 每一小项的指数的变化情况即为k的变化
			 情况，如本例中，每一小项中的i的指数都是每次
			 大i，所以这里的K都是每次加i*/
			  {  
			     c2[k+j]+=c1[j];/*k,j都是指数，他们相加，
			     就是说，同类项合并，也即把同类的系数
			     相加了*/  
			     }
		  for (j=0;j<=n;j++){  
		    c1[j]=c2[j];	
		     c2[j]=0;  
		     }	
		 }	
		 cout<<c1[n]<<endl;
		 }
		 return 0;
}