hdu1028 另一个参考答案

   1 /*
   2   ASUN
   3   杭电1028
   4   方法生成函数（1 + x + x^2 + x^3 + ……）*（1 + x^2 + x^4 + ……）*（1 + x^3 + x^6）……（1 + x^n）
   5   求出x^n前面的系数
   6 
   7 */
   8 
   9 #include <iostream>
  10 #define N 8000
  11 
  12 using namespace std;
  13 int n;
  14 int a[N],b[N],ab[N];//数组a表示一个多项式的系数，下标表示指数 ab表示a和b 乘积
  15 
  16 int Num()
  17 {
  18     int count = 0;
  19     int i,j,k;
  20         
  21     memset(ab, 0 ,sizeof(ab));
  22         for(i = 0; i <= n ; i++)
  23                 ab[i] = 1;//第一次要赋值为全1，为下面循环准备
  24         
  25     for(k = 2; k <= n; k++)
  26     {
  27         
  28         memcpy(b, ab, sizeof(ab));//把ab 复制给 b 开始新的循环
  29 
  30                 for(i = 0; i <= n; i++)
  31                 {
  32                         a[i] = 0;
  33                         ab[i] = 0;
  34                 }
  35                 //初始化数组a 和 ab。也可以试试memset函数我被超时吓怕了
  36 
  37         for(i = 0; i <= n; i += k)
  38             a[i] = 1;//新的一个多项式          
  39 
  40         for(i = 0; i <= n; i++)// 两个多项式相乘
  41             for(j = 0; j <= n; j++)
  42                         {
  43                 ab[i+j] += a[i]*b[j];
  44 
  45                                 if(i + j > n)// 为了不做无谓的操作
  46                                         break;
  47                         }
  48     }
  49     return ab[n];//指数是n的项的系数就是结果
  50 }
  51 
  52 int main()
  53 {
  54     int res;
  55     while(scanf("%d",&n) != EOF)
  56     {
  57         res = Num();
  58         printf("%d\n",res);
  59     }
  60     return 0;
  61 }