题解 P6065 【[USACO05JAN]Sumsets S】
ShineEternal
2020-02-10 16:41:10
上一篇题解貌似没有 code？那窝来补一篇。
[这里是更佳的阅读效果](https://blog.csdn.net/kkkksc03/article/details/104250868)
## description：
给出一个整数 $N$，求将 $N$ 分解为若干个 $2$ 的次幂的和的方案数。
## solution：
这道题可以使用**递推**。
我们由小向大推，分情况讨论：
- $i$ 为奇数：那么只能是 $i-1$ 这个数加上一个 $2^0$ 得来的。
- $i$ 为偶数：可能和上述过程一样，也可能是 $\dfrac{i}{2}$ 再 $\times 2$得来。
所以递推的柿子就显而易见了。
## code:
```cpp
#include<cstdio>
using namespace std;
long long f[1000005];//日常懒得动脑/kk
int main()
{
int n;
scanf("%d",&n);
f[1]=1;//初始化
for(int i=2;i<=n;i++)
{
if(i%2==1)
{
f[i]=f[i-1]%1000000000;
}
else
{
f[i]=(f[i-1]+f[i/2])%1000000000;
}
}
printf("%lld\n",f[n]%1000000000);//这个模数真是。。。别漏看，也别想当然成10^9+7
return 0;
}
```