hdu1028 参考答案

   1 /*
   2 母函数
   3 hdu1028
   4 ymc 2008/09/25
   5 题目大意：
   6 N=a[1]+a[2]+...+a[m],a[i]>0,1<=m<=N。
   7 总共有多少种不同的方程？
   8 4=1+3=3+1是同一种。
   9 解题思路：
  10 f(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)..(1+x^N+...)
  11 其中x^n次方的系数就是构成总值为n的方程总数。
  12 具体参考 生成函数,也叫母函数。
  13 */
  14 #include <iostream>
  15 using namespace std;
  16 const int N=130;
  17 int a[N];
  18 int b[N];
  19 int c[N];
  20 void Poly()
  21 {
  22     memset(c,0,sizeof(c));
  23     for(int i=0;i<N;i++)
  24         for(int j=0;j<N-i;j++)
  25         {
  26             c[i+j]+=a[i]*b[j];
  27         }
  28 }
  29 void Init()
  30 {
  31     memset(a,0,sizeof(a));
  32     memset(c,0,sizeof(c));
  33     for(int i=0;i<N;i++)
  34         a[i]=1;
  35     for(int k=2;k<N;k++)
  36     {
  37         memset(b,0,sizeof(b));
  38         for(int i=0;i<N;i=i+k)
  39         {
  40             b[i]=1;
  41         }
  42         Poly();
  43         memcpy(a,c,sizeof(c));
  44     }
  45 }
  46 int main()
  47 {
  48     int n;
  49     Init();
  50     while(scanf("%d",&n)!=EOF)
  51     {
  52         printf("%d\n",a[n]);
  53     }
  54 }