[文章目录]
Description
给出一个N(1≤N≤10^6)，使用一些2的若干次幂的数相加来求之．问有多少种方法
话说我什么时候菜成这样了，这种题都得找题解。
递推，设f[x]为求x的方法数。如果x是奇数，发现无论怎么分都会有一个1，所以f[x]=f[x-1]。如果x是偶数，分两种情况讨论，如果分出来的树中有1，方案数为f[x-1]，如果没有，那么相当于f[x/2]的方案数，其中每个数都扩大二倍。f[x]=f[x>>1]+f[x-1]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
const ll mod=1000000000;
ll f[1001000];
int main()
{
scanf("%d",&n); f[1]=1;
for(int i=2;i<=n;++i)
{
if(i&1) f[i]=f[i-1];
else f[i]=(f[i-1]+f[i>>1])%mod;
}
printf("%lld",f[n]);
return 0;
}