原题链接
题意
给一个正整数N，问用2的次方可以有几种方案凑出N？
思路
完全背包求方案数。
坑点
不能开longlong,会T。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int f[N];
int a[] = {
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288};
signed main()
{
int n; cin >> n;f[0] = 1;for (int i = 0; i < 20 && a[i] <= n; i ++ ){
for (int j = a[i]; j <= n; j ++ ){
f[j] += f[j - a[i]];f[j] %= 1000000000;}}cout << f[n] << endl;return 0;
}