UOJ310. 【UNR 2】黎明前的巧克力
选定一个集合满足异或和为 $0$ ，然后对于每个数分到两个集合。考虑如何计算所有异或和的集合的大小的 $2$ 次幂的和，考虑函数 $1 + 2x ^ k$ ，其中 $k$ 为这个数。对于所有 $k$ 的异或卷积的 $0$ 次项即为答案。直接对于每个数都 FWT 一次的时间复杂度是不可接受的。分别考虑 $1$ 和 $2x ^ k$ 的贡献。异或 FWT 有 $FWT(a) _ i = \sum _ {j = 0} ^ {2 ^ n - 1} (-1) ^ {|i \wedge j|} a _ j$ ，对于 $0$ 次项，即所有位置贡献；对于 $2x ^ k$ ，在一些位置上贡献 $2$ ，一些位置上贡献 $-2$ 。那么最后一定一些项是 $-1$ ，一些项是 $3$ ；卷积后的答案可以写做 $(-1) ^ a 3 ^ b$ 的形式，其中有 $a + b = n$ 。考虑如何计算 $a, b$ ，我们直接将所有的 $2x ^ k$ 合在一起做一次 FWT ，这样得到 $a - b = f$ 。那么可以解得 $a, b$ ，算出需要的答案。最后还原，将空集答案减去。
查看代码
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
52
53
54
55
| #include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
flag |= c == '-';
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar('0' + x % 10);
}
typedef long long LL;
const int N = 20, M = 1 << N, mod = 998244353, inv2 = 499122177;
int f[M];
int binpow (int b, int k)
{
int res = 1;
for (; k; k >>= 1, b = (LL)b * b % mod)
if (k & 1) res = (LL)res * b % mod;
return res;
}
void fwt (int op)
{
for (int mid = 1; mid < M; mid <<= 1)
for (int i = 0; i < M; i += mid << 1)
for (int j = 0; j < mid; ++j)
{
int p = f[i | j], q = f[i | mid | j];
f[i | j] = (LL)(p + q) * op % mod, f[i | mid | j] = (LL)(p - q) * op % mod;
}
}
int main ()
{
int n; read(n);
for (int i = 1, a; i <= n; ++i)
read(a), ++f[a];
fwt(1);
for (int i = 0; i < M; ++i)
f[i] = ((n - f[i]) / 2 & 1 ? -1 : 1) * binpow(3, (n + f[i]) / 2);
fwt(inv2);
write((f[0] - 1 + mod) % mod);
return 0;
}
|