Uva 10334

这道题几乎和UVa 495是一样的。
 1 #include<iostream>
 2 #include<cstdio>
 3 #define mod 1000000
 4 using namespace std;
 5 const int maxn = 1005;
 6 const int len = 300;
 7 int f[maxn][maxn];
 8 
 9 int main()
10 {
11     f[0][0] = 1, f[1][0] = 2;
12     for (int i = 2; i <= 1001; i++)
13     {
14         int c = 0;
15         for (int j = 0; j <= len; j++)
16         {
17             int t = f[i - 1][j] + f[i - 2][j]+c;
18             f[i][j] = t%mod;
19             c = t / mod;
20         }
21     }
22     int n;
23     while (scanf("%d",&n)==1)
24     {
25         int pos = 0;
26         for (int i = len; i >= 0; i--) {
27             if (f[n][i] > 0) {
28                 pos = i; break;
29             }
30         }
31         printf("%d", f[n][pos]);
32         for (int i = pos - 1; i >= 0; i--)
33             printf("%06d", f[n][i]);
34         printf("
");
35     }
36     return 0;
37 }