1 /*
   2   SUN
   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 i,j,k;
  19         
  20     memset(ab, 0 ,sizeof(ab));
  21         for(i = 0; i <= n ; i++)
  22           ab[i] = 1;//第一次要赋值为全1，为下面循环准备
  23         
  24     for(k = 2; k <= n; k++)
  25     {
  26         
  27         memcpy(b, ab, sizeof(ab));//把ab 复制给 b 开始新的循环
  28 
  29         for(i = 0; i <= n; i++)
  30         {
  31                 a[i] = 0;
  32                 ab[i] = 0;
  33         }
  34         //初始化数组a 和 ab。也可以试试memset函数我被超时吓怕了
  35 
  36         for(i = 0; i <= n; i += k)
  37             a[i] = 1;//新的一个多项式          
  38 
  39         for(i = 0; i <= n; i++)// 两个多项式相乘
  40             for(j = 0; j <= n; j++)
  41                 {
  42                    ab[i+j] += a[i]*b[j];
  43                    if(i + j > n)// 为了不做无谓的操作
  44                         break;
  45                 }
  46     }
  47     return ab[n];//指数是n的项的系数就是结果
  48 }
  49 
  50 int main()
  51 {
  52     int res;
  53     while(scanf("%d",&n) != EOF)
  54     {
  55         res = Num();
  56         printf("%d\n",res);
  57     }
  58     return 0;
  59 }