题意
对于集合 $T \subseteq { 0,1,2,\cdots }$，定义函数 $f(T) = \sum \limits _{i \in T} 2^i$，也就是每个数出没出现对应一个二进制数。
给定集合 $V_0,V_1,\cdots,V_{2^n - 1}$，求所有的集合 $S$，使得对于所有 $T \subseteq { 0,1,2,\cdots}$，都有 $|S\cap T| \in V_{f(T)}$。也就是，对于每一个 $T$，你的 $S$ 和 $T$ 的共同元素个数是 $V_{f(T)}$ 中的某一个。
解法
从 $0$ 开始依次考虑每一个元素是否在 $S$ 里面。如果 $i$ 在 $S$ 里面，所有包含 $i$ 的 $T$ 对应的 $V_{f(T)}$ 可以选的数就都要减一，因为选了一个 $i$。对于两个集合 $T_1$ 和 $T_2$，如果它们只在有没有 $i$ 上不一样，其中 $T_1$ 包含 $i$，那么两个集合可以合并成一个：$V_{f(T’)}=(V_{f(T_1)} >> 1) \cap V_{f(T_2)}$。同理，如果 $i$ 不在 $S$ 里面，则 $V_{f(T’)}=V_{f(T_1)} \cap V_{f(T_2)}$。
发现两个集合可以合并成另外两个集合，每考虑一个 $i$ 后集合总数不变。可以把新合并出来的集合存在原来两个集合的位置，类似 FFT（？）。对于每个 $i$ 直接暴力合并，总时间复杂度为 $O(n 2^n)$。
代码：
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>
#include <vector>
using namespace std;
int n;
int a[2000010],nw[2000010];
vector <int> Ans;
int main()
{
scanf("%d",&n);
a[0] = (1 << (n + 1)) - 1;
for (int i = 1;i < (1 << n);i ++) scanf("%d",a + i);
for (int i = 0;i < n;i ++)
{
for (int w = 0;w < (1 << n);w += (1 << (i + 1)))
{
for (int j = w;j < w + (1 << i);j ++)
{
int k = j + (1 << i);
int tmpa = a[j],tmpb = a[k];
a[k] = (tmpa & (tmpb >> 1));
a[j] = (tmpa & tmpb);
nw[k] = nw[k] ^ (1 << i);
}
}
}
for (int i = 0;i < (1 << n);i ++)
if (a[i] & 1) Ans.push_back(nw[i]);
printf("%d\n",Ans.size());
for (int i : Ans) printf("%d\n",i);
}
|