题目：

题目大意：就是拆分n 每一位都得是2的幂。 

注意4 ：1111    112   22   4   一共4种

递推：

对于n可以分为是奇数还是偶数

奇数：肯定有1，  和去掉一个1的情况一样  所以 dp[i] = dp[i-1]

偶数：有1的话，肯定有两个1，dp[i] = dp[i-2]    没有1的话，每一位都是2的倍数，dp[i] = dp[i/2]   总的：dp[i] = dp[i-2] + dp[i/2]

打表：

n          2    3   4  5   6   7      8      9  

sum     2    2   4  4   6   6     10    10

例如：

偶数2：   11   2

奇数3：   111   12                     去掉一个1： { 11  2 } = dp[2]   

偶数4：   1111  112   22   4

偶数6：   111111  11112    1122    222    24   114  {

               有1的情况： 111111   11112   1122   114  去掉两个1：{ 1111    112   22   4 } = dp[4]

               没有1的情况   222   24                                 除以2 ：{111   12 } = dp[3]

               总的    dp[6] = dp[4] + dp[3]

               }

AC代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
         #define MOD 1000000007using namespace std; const int maxn = 1e7+10;long long a[maxn]; void init(){    memset( a, 0, sizeof( a));} int main(){    init();    a[0] = a[1] = 1;    for ( int i = 2; i <= 10000000; ++ i) {        if ( i & 1) {//奇数            a[i] = a[i - 1];        }        else{            a[i] = a[i / 2] % MOD + a[i - 2] % MOD;//注意取模        }        a[i] = a[i] % MOD;    }    int n;    while(~scanf( "%d", &n)){    cout << a[n] << endl;    }}