题目1084：整数拆分 (递推)

 1 #include<stdio.h>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #include<set>
11 
12 using namespace std;
13 
14 typedef long long ll;
15 
16 const int mod = 1000000000;
17 int f[1000010];
18 
19 void init()
20 {
21     f[1] = 1;
22     for(int i=2;i<=1000000;i++)
23     {
24         if(i&1) f[i] = f[i-1]%mod;
25         else f[i] = (f[i-1]+f[i/2])%mod;
26     }
27 }
28 
29 int main()
30 {
31     int n;
32     init();
33     while(~scanf("%d",&n))
34     {
35         printf("%d\n",f[n]);
36     }
37     return 0;
38 }