⇤ ← 于2008-10-10 22:28:32修订的的版本1
1339
备注:
|
← 于2008-10-11 17:37:14修订的的版本2 ⇥
1325
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 4: | 行号 4: |
ASUN | SUN |
行号 20: | 行号 20: |
int count = 0; | |
行号 25: | 行号 24: |
ab[i] = 1;//第一次要赋值为全1,为下面循环准备 | ab[i] = 1;//第一次要赋值为全1,为下面循环准备 |
行号 32: | 行号 31: |
for(i = 0; i <= n; i++) { a[i] = 0; ab[i] = 0; } //初始化数组a 和 ab。也可以试试memset函数我被超时吓怕了 |
for(i = 0; i <= n; i++) { a[i] = 0; ab[i] = 0; } //初始化数组a 和 ab。也可以试试memset函数我被超时吓怕了 |
行号 44: | 行号 43: |
{ ab[i+j] += a[i]*b[j]; if(i + j > n)// 为了不做无谓的操作 break; } |
{ ab[i+j] += a[i]*b[j]; if(i + j > n)// 为了不做无谓的操作 break; } |
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 }