【题目描述】
给定整数$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$然后跑个板子就行了。。。
借下学长代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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\n",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]$这个东西用前缀和维护一下就行
这么简单的结论我没想到 我太蒻了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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\n", a[n]);
return 0;
}

时间复杂度$O(n)$

评论