Blog
0%

CodeForces Global Round 2 H

发表于

题目大意

给定 $n$ 个可重集 $S_i$ 及 $x,y,z,k$，每个可重集仅包含三种元素 $a_i,b_i,c_i$，且它们的个数分别为 $x,y,z$。对于每个 $t\in[0,2^k-1]$ 求
$$
\sum_{p_1\in S_1}\sum_{p_2\in S_2}\cdots\sum_{p_n\in S_n} [p_1\oplus p_2\oplus\cdots\oplus p_n=t]
$$
其中 $\oplus$ 表示按位异或。

$n\le 10^5,a_i,b_i,c_i< 2^k,k\le 17$。

题解

题目即求二进制 $n$ 维循环卷积，直接暴力 FWT 是 $\mathcal{O}(nk2^k)$ 的，而注意到每个集合元素个数均相等，考虑从这方面入手分析。

下文用集合的形式表示二进制相关运算。

设 $m=2^k$，记 $\mathcal{F}:\mathbb{R}^m\to\mathbb{R}^m$ 为异或的沃尔什变换，$F[i]$ 表示 $F$ 在 $i$ 处的点值。

设答案的形式幂级数为 $G$，$n$ 个集合的形式幂级数为 $F_i$，则根据上文的暴力有
$$
\mathcal{F}(G)[k]=\prod_{i=1}^n\mathcal{F}(F_i)[k]
$$
对于特定的 $i$，讨论 $\mathcal{F}(F)[k]$，展开得到
$$
\mathcal{F}(F)[k]=\sum_{i=0}^{m-1}(-1)^{|i\cap k|}F[i]
$$
而 $F$ 仅在 $a,b,c$ 处取到非零值，带入有
$$
\mathcal{F}(F)[k]=(-1)^{|a\cap k|}x+(-1)^{|b\cap k|}y+(-1)^{|c\cap k|}z
$$
带入到原式得到
$$
\mathcal{F}(G)[k]=\prod_{i=1}^n(-1)^{|a_i\cap k|}x+(-1)^{|b_i\cap k|}y+(-1)^{|c_i\cap k|}z
$$
注意到右边即为 $8$ 个不同式子相乘，这里有一个小 trick 是先将所有 $a_i,b_i,c_i$ 异或上 $a_i$，最后算答案时还原回来，则原式转化成
$$
\mathcal{F}(G)[k]=\prod_{i=1}^nx+(-1)^{|b_i\cap k|}y+(-1)^{|c_i\cap k|}z
$$
这样变成了 $4$ 个不同的式子相乘，设 $s_1=x+y+z,$ $s_2=x+y-z,$ $s_3=x-y+z,$ $s_4=x-y-z$，则
$$
\mathcal{F}(G)[k]=\prod_{i=1}^4s_i^{p_i}
$$
问题转化为对任意 $k$ 求 $p_i$，则我们至少需要 $4$ 个方程，首先方案总和为 $n$，即
$$
\begin{align}
p_1+p_2+p_3+p_4=n\\
\end{align}
$$
不妨单独考虑 $y,z$ 前的系数，可以分 $3$ 种情况。

  1. 只考虑 $y$ 前的系数，即 $$\sum_{i=1}^n(-1)^{|b_i\cap k|}=\sum_{i=0}^{m-1}(-1)^{|i\cap k|}\sum_{j=1}^n[b_j=i]$$
    考虑构造 $H_1\in \mathbb{R}^m$，其中只有 $b_i$ 会对 $H_1$ 产生贡献，则 $$\sum_{i=0}^{m-1}(-1)^{|i\cap k|}\sum_{j=1}^n[b_j=i]=\sum_{i=0}^{m-1}(-1)^{|i\cap k|}H[i]=\mathcal{F}(H_1)[k]$$
    同时显而易见的是，当 $s_i$ 中的 $y$ 取到正号时，$p_i$ 对系数有正的贡献，负号反之，即 $$\begin{align}p_1+p_2-p_3-p_4=\mathcal{F}(H_1)[k]\end{align}$$
  2. 只考虑 $z$ 前的系数，同理构造 $H_2\in\mathbb{R}^m$，其中只有 $c_i$ 会对 $H_2$ 产生贡献，得到 $$\begin{align}p_1-p_2+p_3-p_4=\mathcal{F}(H_2)[k]\end{align}$$
  3. 同时考虑 $y,z$ 前的系数，即 $$\begin{aligned}\sum_{i=1}^n(-1)^{|b_i\cap k|}(-1)^{|c_1\cap k|}&=\sum_{i=0}^m(-1)^{|i\cap k|}H_1[i](- 1)^{|i\cap k|}H_2[i]\\&=\mathcal{F}(H_1)[k]\cdot\mathcal{F}(H_2)[k]\end{aligned}$$
    自然地构造出 $H_3\in\mathbb{R}^m$，只有 $b_i\oplus c_i$ 会对 $H_3$ 产生贡献，则 $$\sum_{i=1}^n(-1)^{|b_i\cap k|}(-1)^{|c_1\cap k|}=\mathcal{F}(H_1)[k]\cdot\mathcal{F}(H_2)[k]=\mathcal{F}(H_3)[k]$$
    不难发现，当 $s_i$ 中的 $y,z$ 同号时，对系数有正的贡献，异号反之，则列得最后一个方程 $$\begin{align}p_1-p_2-p_3+p_4=\mathcal{F}(H_3)[k]\end{align}$$

联立 $(1)\ (2)\ (3)\ (4)$ 式解得
$$
\begin{cases}
p_1=(\mathcal{F}(H_1)[k]+\mathcal{F}(H_2)[k]+\mathcal{F}(H_3)[k]+n)/4\\
p_i=(\mathcal{F}(H_{i-1})[k]-2p_1)/2&\forall{i\in[2,4]}
\end{cases}
$$
时间复杂度 $\mathcal{O}((\log n+k)2^k)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n, k, x, y, z, res = 0;
std::cin >> n >> k >> x >> y >> z;
std::vector<int> f1(1 << k), f2(1 << k), f3(1 << k), g (1 << k);
for (int i = 0, a, b, c; i < n; ++i) {
    std::cin >> a >> b >> c;
    res ^= a, b ^= a, c ^= a;
    f1[b] += 1, f2[c] += 1, f3[b ^ c] += 1;
}
FWT(f1, false), FWT(f2, false), FWT(f3, false);
int s1 = int(x) + y + z, s2 = int(x) + y - z,
    s3 = int(x) - y + z, s4 = int(x) - y - z;
for (int i = 0; i < (1 << k); ++i) {
    int c1 = (f1[i] + f2[i] + f3[i] + n) / 4;
    int c2 = (f1[i] + n - 2 * c1) / 2;
    int c3 = (f2[i] + n - 2 * c1) / 2;
    int c4 = (f3[i] + n - 2 * c1) / 2;
    g[i] = s1.power(c1) * s2.power(c2)
         * s3.power(c3) * s4.power(c4);
}
FWT(g, true);
for (int i = 0; i < (1 << k); ++i) std::cout << g[i ^ res] << " ";