方法：DP
f[i]表示i分解成若干2的幂次的和的方案数.
i= 0 1 2 3 4 5 6 7 ...
f[i]= 0 1 2 2 4 4 6 6 ...
规律: 若i为奇数,则f[i]=f[i-1];
若i为偶数,则f[i]=f[i-1]+f[i/2].
证明: 若i为奇数,则必有1,因为1=2^0,所以减一后得f[i-1].
若i为偶数,则:
取一个1出来,则f[i]=f[i-1];
不取1出来,则因为i为偶数,f[i]=f[i/2].
综上,有:
f[0]=0,f[1]=1;
转移方程:f[i]=f[i-1]+((!(i%2))?f[i/2]:0).

------------不怎么华丽的分割线------------

但是因为n<=1e8,所以不可以定义1e8的数组.
那么利用i为奇数时f[i]=f[i-1],定义f[N/2]的数组,
并且可得:
若i<=1,则特判;
若i>1,则首先由1(0和1共用0)到n/2计算出f,
然后算出f[n/2]即可.

标程：

#include<bits/stdc++.h>
#define N 50000009
#define mod 100000007
using namespace std;
int n,f[N];
int main() {
    cin>>n; f[0]=1;
    if (n==0) cout<<0<<endl;
    else if (n==1) cout<<1<<endl;
    else {
        for (int i=1;i<=n/2;i++) f[i]=(f[i-1]%mod+f[i/2]%mod+mod)%mod;
        cout<<f[n/2]%mod<<endl;
    }
    return 0;
}