- 题目链接：2048
- 题目思路：这种鬼题一看就要用dp，我们不妨用数组f[i]表示组成i的方案数，根据题意，有用的数是2的整数次幂，但最后答案的方案数要乘上2的无用的数次幂，我们可以用一个数组来存有用的数，以便于判断。
- 代码
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
int sc() {
int xx = 0, ff = 1; char cch;
while (cch < '0' || cch > '9') {
if (cch == '-') ff = -1; cch = gc;
}
while (cch >= '0'&& cch <= '9') {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
int num[2500];
int n, tot;
ll f[2500];
int main() {
for (int i = 0; i <= 11; i++) //用num数组来存有用的数
num[1<<i] = i;
n = sc();
for (int i = 1; i <= n; i++) {
int x = sc();
if(!num[x] && x != 1) { // 要特判1
tot++; //无用数+1
continue;
}
for (int j = 2048; j >= 1; j--) { //倒序，相当于01背包，每个数只能用一次
if(f[j]) {
if(j + x <= 2048) //输入的数+循环的到的数小于2048
f[j + x] = (f[j + x] + f[j]) % mo; //方案数相加
else f[2048] = (f[2048] + f[j]) % mo; //否则方案数加给2048
}
}
f[x]++; //不要忘记给输入的数的方案数+1
}
// cout << tot << endl;
for(int i = 1; i <= tot; i++) { //根据题意，最后答案要乘2的无用数数目次幂
f[2048] = (f[2048] * 2ll) % mo;
}
printf ("%lld\n", f[2048]);
return 0;
}