hdu1398 参考答案

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