对于一个非空集合{$a_i$},我们称一个集合是 $magical$ 的,当且仅当它满足以下两个条件。
1:$a_1$ & $a_2$ &…& $a_n$ =0(&表示 $and$)
2:{$a_i$} 的任意一个除它本身外的非空子集不满足1。
小 $A$ 有一个很大很大的集合。很显然这个集合的子集数量是一个天文数字。
小 $A$ 现在想要知道这个集合的 magical 的非空子集数量是多少。
为了防止不必要的麻烦,请将答案 $mod$ $1e9+7$ 后输出。
输入
第一行一个整数 $T$ 表示数据组数
接下来每组数据第一行一个整数 $n$,表示集合元素数量。
第二行 $n$ 个整数,表示这个集合中的元素。
输出
输出共 $T$ 行,对应这组数据的答案。
样例数据
输入
输出
题解
来自hzq84621
为了方便我们把题意改成集合内元素 $or$ 和等于 $511$。
考虑一个数,假如他左边的已有部分 $or$ 和$=l$,右边的已有部分 $or$ 和 $=r$,考虑用 $dp[i][j][k]$ 表示已经做到第 $i$ 个数,$1$ 到 $i$ 个数 $or$ 的和是 $j,k$ 是第
$i+1$ 个数到第 $n$ 个数的 $or$ 和的子集。
这样好像就比较清晰了。
不选第 $i+1$ 个数,$dp[i][j][k]->dp[i+1][j][k]$
选第 $i+1$ 个数(需要保证 $a[i+1]|j!=j$)
$dp[i][j][k]->dp[i+1][j|a[i+1]][p]$
$p$ 需要满足 $p$ 是 k^(k&a[i+1]) 的父集而且 $p$ 不是 a[i+1]^(a[i+1]&j) 的父集
否则会导致 $a[i+1]$ 是多余的。
好像不太好算?
考虑容斥,先选了不管他,然后容斥掉不合法的情况对答案的贡献。
只有三个转移方程的 dp,我都不知道说甚么。
可以发现 k 一定是 j 的子集否则没有意义。
时间复杂度$O(3^{log 2 (a[i])} \times n \times T)$
代码
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
48
49
50
51
| #include <bits/stdc++.h>
const int mod = 1000000007;
const int IN_LEN = 1 << 20, OUT_LEN = 1 << 20;
char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf, *oh = obuf;
inline void read(int &x) { for (x = 0; !isdigit(*ih); ih++); while (isdigit(*ih)) x = (x << 1) + (x << 3) + ((*ih++) ^ '0'); }
inline void write(int x) {
static int buf[30], cnt;
if (!x) *oh++ = 48;
else {
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) *oh++ = buf[cnt--];
}
}
int f[101][512][512];
int n, T;
inline void solve() {
read(n);
for (register int i = 0; i <= n; i++) {
for (register int j = 0; j < 512; j++) {
for (register int k = j; ; (--k) &= j) {
f[i][j][k] = 0;
if (!k) break;
}
}
}
f[0][0][0] = 1;
for (register int i = 0, x; i < n; i++) {
read(x), x = 511 - x;
for (register int j = 0; j < 512; j++) {
for (register int k = j; ; (--k) &= j) {
if (f[i][j][k]) {
f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % mod;
if ((x & j) != x) {
f[i + 1][j | x][k - (k & x)] = (f[i + 1][j | x][k - (k & x)] + f[i][j][k]) % mod;
f[i + 1][j | x][(k - (k & x)) | (x - (x & j))] = (f[i + 1][j | x][(k - (k & x)) | (x - (x & j))] - f[i][j][k]) % mod;
}
}
if (!k) break;
}
}
}
if (f[n][511][0] < 0) f[n][511][0] += mod;
write(f[n][511][0]), *oh++ = '\n';
}
int main() {
fread(ibuf, 1, IN_LEN, stdin);
read(T);
while (T--) solve();
fwrite(obuf, 1, oh - obuf, stdout);
return 0;
}
|
