FWT + 解方程 高级版
题意
给定常数 $k \le 17$ 和常数 $x, y, z \le 10^9$ ，现在有 $n \le 10^5$ 个数组，对于每个数组，给定 $a_i, b_i, c_i \le 2^k$ ，表示该数组有 $x$ 个 $a_i$ ， $y$ 个 $b_i$ ， $z$ 个 $c_i$ ，现在从每个数组中选一个数字异或起来得到 $sum$ ，对于每个 $sum \in [0, 2^k)$ ，输出方案数
思路
先考虑暴力 FWT ：构造幂级数 $f_i(t) = xt^{a_i} + yt^{b_i} + zt^{c_i}$ ，定义幂级数乘法为异或卷积，那么设 $F = \prod f_i$ ，则 $F[i]$ 即为 $sum = i$ 的方案数，直接暴力 FWT 是 $O(nk2^k)$
任然考虑手玩一下 FWT ，记幂级数 $f’ = FWT(f)$ ，有 $f’[s] = (-1)^{\mid a_i \& s\mid} x + (-1)^{\mid b_i \& s\mid} y + (-1)^{\mid c_i \& s\mid} z$ $f’[s] = (-1)^{\mid a_i & s\mid} x + (-1)^{\mid b_i & s\mid} y + (-1)^{\mid c_i & s\mid} z$
这有点痛苦，考虑把三元组 $(a_i, b_i, c_i)$ 变成 $(a_i \oplus c_i, b_i \oplus c_i, 0)$ ，记 $C = c_1 \oplus c_2 \oplus … \oplus c_n$ ，最后 $sum$ 的答案存在 $sum \oplus C$ 处；以下的讨论中，$a, b, sum$ 都是已经变换了的
那么 $f’[s] = (-1)^{\mid a_i \& s\mid} x + (-1)^{\mid b_i \& s\mid} y + z$ $f’[s] = (-1)^{\mid a_i & s\mid} x + (-1)^{\mid b_i & s\mid} y + z$ ，就只有四种情况：
- $x + y + z$
- $x - y + z$
- $-x + y + z$
- $-x - y + z$
不妨记以上四种情况出现的次数分别为 $d_1, d_2, d_3, d_4$ ，可得： $F’[s] = (x + y + z)^{d_1}(x - y + z)^{d_2}(-x + y + z)^{d_3}(-x - y + z)^{d_4}$ ，于是问题变成求 $d_1, d_2, d_3, d_4$
考虑解方程，我们现在有 $d_1 + d_2 + d_3 + d_4 = n$ ，还要再找到 $3$ 个方程，我们使用 FWT 找方程：
- 构造 $G(t) = \sum_{i = 1}^{n} t^{a_i}$ ，那么 $G’[s] = (-1)^{\mid s \& a_i \mid}$ $G’[s] = (-1)^{\mid s & a_i \mid}$ ，即只有 $x$ 符号的贡献，那么有 $G’[s] = d_1 + d_2 - d_3 - d_4$ ，不妨记作 $d_1 + d_2 - d_3 - d_4 = p_1$
- 同理构造 $G(t) = \sum_{i = 1}^{n} t^{b_i}$ ，有 $G’[s] = d_1 + d_3 - d_2 - d_4$ 不妨记作 $d_1 - d_2 + d_3 - d_4 = p_2$
- 最后再构造 $G(t) = \sum_{i = 1}^{n} t^{a_i \oplus b_i}$ ，有 $G’[s] = d_1 + d_4 - d_2 - d_3$ ，不妨记作 $d_1 - d_2 - d_3 + d_4 = p_3$
于是我们有：
$$
\begin{cases}
d_1 + d_2 + d_3 + d_4 = n \\
d_1 + d_2 - d_3 - d_4 = p_1 \\
d_1 - d_2 + d_3 - d_4 = p_2 \\
d_1 - d_2 - d_3 + d_4 = p_3
\end{cases}
$$
手玩解得：
$$
\begin{cases}
d_1 = \frac{n + p_1 + p_2 + p_3}{4} \\
d_2 = \frac{n + p_1 - p_2 - p_3}{4} \\
d_3 = \frac{n - p_1 + p_2 - p_3}{4} \\
d_4 = \frac{n - p_1 - p_2 + p_3}{4}
\end{cases}
$$
时间复杂度 $O(k2^k)$
代码
1 |
|