http://poj.org/problem?id=2229
挺好的一公式。。
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 using namespace std; 7 #define N 1000010 8 #define mod 1000000000 9 long long dp[N]; 10 int a[N]; 11 int main() 12 { 13 int i,j,k,n; 14 while(cin>>n) 15 { 16 memset(dp,0,sizeof(dp)); 17 memset(a,0,sizeof(a)); 18 dp[1] = 1; 19 dp[2] = 2; 20 dp[3] = 2; 21 dp[4] = 4; 22 for(i = 5; i <= n ; i++) 23 { 24 if(i%2!=0) 25 dp[i] = dp[i-1]; 26 else 27 { 28 dp[i] = (dp[i-2]+dp[i/2])%mod; 29 } 30 } 31 cout<<dp[n]%mod<<endl; 32 } 33 return 0; 34 }