44 lines
2.2 KiB
C++
44 lines
2.2 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int MOD = 1e9 + 7; //取模
|
||
const int N = 1 << 24; //最多24个数字
|
||
int n; //实际n个数字
|
||
int k; //k个不允许出现的数字
|
||
int full; //将所有位置全部为1时的拉满状态，对应的十进制数
|
||
unordered_set<int> no_permit; //有哪些数字是不允许出现在前缀和中的
|
||
int f[N]; //f[i]表示状态为i时的方案数
|
||
LL sum[N]; //sum[i]表示当状态为i时的前缀和
|
||
|
||
//一般状态压缩DP，n<=12,这里的n<=24，看来暴力的状态压缩要挂~
|
||
int lowbit(int x) {
|
||
return x & (-x);
|
||
}
|
||
|
||
int main() {
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) cin >> sum[1 << i]; //按二进制位置映射的十进制数来存储(状态压缩式的存储方法)
|
||
//前缀和不允许出现的数字
|
||
cin >> k;
|
||
int x;
|
||
for (int i = 0; i < k; i++)cin >> x, no_permit.insert(x);
|
||
|
||
//状态为0时，表示一个全部都不选择，那么前缀和是0，肯定不在给定的k个正整数之中。因为正整数都大于0，这是一种唯一方案。
|
||
f[0] = 1, full = (1 << n) - 1;//满状态
|
||
//枚举现在的状态
|
||
for (int i = 1; i <= full; i++) {
|
||
//每次新的状态（sum[i]） = 仅有末尾1的状态 + 去掉末尾1的状态，而二者都在先前求过了，可以O(1)的求出sum[i] 的值
|
||
sum[i] = sum[i & ~lowbit(i)] + sum[lowbit(i)];
|
||
//sum[i] += sum[i - 1]; 这种传统方法是不可以的，因为sum数组并不是按一个个数字按次序保存的，而是按二进制数位方式保存的
|
||
//这所以这样保存，是因为状态压缩DP，是需要枚举每一个数位，每个数位与传统方式的前缀和不符，需要特殊记忆一下这个方法
|
||
//如果前缀和等于限定的数，那么是不合法的
|
||
if (no_permit.count(sum[i]))continue;
|
||
|
||
//快速找到所有位置为1的
|
||
for (int j = i; j; j -= lowbit(j))//枚举可能的上一次状态
|
||
f[i] = (f[i] + f[i & ~lowbit(j)]) % MOD; //去掉j位为1的 i & ~lowbit(j)
|
||
}
|
||
printf("%d\n", f[full]);
|
||
return 0;
|
||
} |