题意大意是有一个整数,可以用若干个 2的 n次幂累加得到,问一共有多少种累加方案
统计方案的题,最重要的是做到不重复,不遗漏
dp[i][0]表示构成 i中不含 1的方案有多少种
dp[i][1]表示构成 i中含 1个 1的方案有多少种
dp[i][2]表示构成 i中含 1的方案有多少种
最后答案是 dp[N][0] +dp[N][2]
思路如下:
1) 如果 i是奇数,那么必然要有 1,含一个 1的方案可以通过 i-1不含 1的方案,在后面加一个 1得到
所以 dp[i][0] = 0, dp[i][1] = dp[i-1][0]
2) 如果 i是偶数,那么不可能有单独的 1,不含 1的方案可以通过 i/2的情况得到
因为 i/2这个数的所有方案,乘以 2以后就不含 1
所以 dp[i][0] = (dp[i/2][0] +dp[i/2][1]), dp[i][1] = 0
3) 而含 1的情况,可以通过 i-1 的所有情况,在后面加一个 1,即是 i含 1的所有情况
所以 dp[i][1] = (dp[i-1][0] + dp[i-1][1])
之所以要选择 1进行讨论,是因为 1这个数太特殊了
在构成 i的过程中,肯定有一种 i个 1加起来的情况
而其他的情况均可建立这个基础上,把若干个 1缩成 2的 n次幂 (有点像 2048)
不过这题貌似也可以用背包做: dp[i][j] 表示组成 i的最大的数为 2j 的方案数
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
#define Pow2(a) a*a
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<?(-a):a;}
const int MOD=,maxn=+;
int N;
int pow2[];
LL dp[maxn][];
int main()
{
pow2[]=;
for(int i=; i<; i++) pow2[i]=pow2[i-]*;
dp[][]=;dp[][]=dp[][]=;
for(int i=; i<maxn; i++)
{
if(i&)
{
dp[i][]=;
dp[i][]=dp[i-][];
}
else
{
dp[i][]=((LL)dp[i/][]+dp[i/][])%MOD;
dp[i][]=;
}
dp[i][]=((LL)dp[i-][]+dp[i-][])%MOD;
}
while(~scanf("%d", &N))
{
if(N==){puts("1");continue;}
printf("%d\n", ((LL)dp[N][]+dp[N][])%MOD);
}
return ;
}