整数划分

【题目描述】
给定整数 (N)，求分解成(2)的幂的方案数。结果(Mod 1000000007),比如 (N = 7) 时，共有 (6) 种划分方法。
(7=1+1+1+1+1+1+1 \ =1+1+1+1+1+2 \ =1+1+1+2+2 \ =1+2+2+2 \ =1+1+1+4 \ =1+2+4 \)

【输入格式】
输入一个数(N)。((1 le N le 10^6))

【输出格式】
输出划分方法的数量 (Mod 000000007)

第一眼看好像是结论题 于是推了好久的结论。。。没推出来 然后就去写DP
结果到最后也只写了个错误的背包

做法1 完全背包
物品就是(2^0 2^1 2^2 cdots) 然后跑个板子就行了。。。
借下学长代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000000 
#define mod 1000000007 
using namespace std;
typedef long long ll;
int n;
int sz;
int bin[maxn+5];
ll dp[maxn+5];
int main(){
	scanf("%d",&n);
	bin[0]=1;
	while(bin[sz]*2<=n){
		sz++;
		bin[sz]=bin[sz-1]*2;
	} 
	dp[0]=1;
	for(int i=0;i<=sz;i++){
		for(int j=bin[i];j<=n;j++){
			dp[j]+=dp[j-bin[i]];
			dp[j]%=mod;
		}
	}
	printf("%lld
",dp[n]);
}

时间复杂度 (O(n log n))

做法2 递推
可以分别考虑将当前数字拆分出几个1
设(f[i])代表(i)有多少种拆分方案
以(f[9])为例 如果把9拆分成1个1 和 其他一些数字 则方案数就等于(将8用2, 4, 8拆分的方案数) 其实也就是 (将4用1, 2, 4拆分的方案数) 即(f[4])
同理 把9拆分成3个1和其他数字时 方案数会是 (f[3])
所以可以得出结论 (f[n] = sum_{i=1}^{n/2} f[i]) 这个东西用前缀和维护一下就行
这么简单的结论我没想到 我太蒻了

代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

const ll mod = 1000000007;
ll n, ans;
ll a[1000005], sum[1000005];

ll read() {
	ll ret = 0, flag = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		ret = (ret << 3) + (ret << 1) + (ch ^ '0');
		ch = getchar();
	}
	return ret * flag;
}

int main() {
	n = read();
	a[1] = 1; sum[1] = 2;
	a[0] = 1; sum[0] = 1;
	for (int i = 2; i <= n; i++) {
		a[i] = sum[i/2]; sum[i] = (sum[i-1] + a[i]) % mod;
	}
	printf("%lld
", a[n]);
	return 0;
} 

时间复杂度(O(N))