题解 CF1336E2 【Chiori and Doll Picking (hard version)】

更好的阅读体验：https://memset0.cn/cf1336e2 这篇题解是出题人把刀架在我脖子上写的，锅了不关我事（雾 --- 给定 $n$ 个整数 $\langle a_1, a_2 ... a_n \rangle$，在 $[0; 2^m)$ 的范围内。对于 $k \in [0; m]$，求选出一个子集使得异或和的二进制表示有 $k$ 个 $1$ 的方案数。 $1 \leq n \leq 2 \times 10^5,\ 0 \leq m \leq 53$。 --- ## 0x00 做题之前，最重要的： **当然是膜此题出题人 Sooke 大神**！ ## 0x01 定义： - $\operatorname{popcount}(x)$ 表示 $x$ 的二进制表示下 $1$ 的个数 - $\langle i, j \rangle = \operatorname{popcount(i \& j)}$ 对于线性基 $S$，定义： - $\operatorname{span}(S)$ 表示 $S$ 张成的向量空间 - $F(S) = \sum_{x \in \operatorname{span}(S)} z^x$ - $P(S) = \sum_{x \in \operatorname{span}(S)} z^{\operatorname{popcount}(x)}$ 对于此题，定义 - $A$ 为由题中给定数得到的线性基 首先你已经会了一个 $O(2^{\operatorname{rank}(A)})$ 的暴力，下文我们介绍一种 $O(2^{m-\operatorname{rank}(A)})$ 的算法，就可以通过分治在 $O(2^{m/2})$ 的时间复杂度内通过本题。 ## 0x02 由线性基的基本性质，可以得到： $$ (z^x) * F(A) = F(A) $$ 在此基础上枚举 $x \in \operatorname{span}(A)$ 有 $$ \begin{aligned} F(A) * F(A) &= F(A) \cdot 2^{\operatorname{rank}(A)} \\ \operatorname{FWT}(F(A)) \cdot \operatorname{FWT}(F(A)) &= \operatorname{FWT}(F(A)) \cdot 2^{\operatorname{rank}(A)} \end{aligned} $$ 由于是按位相乘，考虑方程 $x^2=x+1$ 的实根仅有 $\left\{ \begin{aligned} x_1 &= 0 \\ x_2 &= 2^{\operatorname{rank}(A)} \end{aligned} \right.$，故 $[z^i] \operatorname{FWT}(F(A)) \in \{0, 2^{\operatorname{rank}(A)}\}$。 ## 0x03 让我们再回到 $\operatorname{FWT}$ 运算本身的意义： $$ \begin{aligned} [z^i] \operatorname{FWT}(F(A)) &= \sum_{x \in \operatorname{span}(A)} (-1)^{\langle i,x \rangle} \\ &\in \{ 0, 2^{\operatorname{rank}(A)} \} \\ \end{aligned} $$ 如果存在 $x$ 使得 $(-1)^{\langle i,x \rangle} = -1$，则 $\operatorname{FWT}(A)_i$ 只能为 $0$。 $\langle x,y \rangle$ 和 $\oplus$ 运算满足结合律： $$ \langle i,x \rangle \oplus \langle j,x \rangle = \langle i \oplus j, x \rangle $$ 可以通过把 $\&$ 理解为二进制按位乘法，$\oplus$ 理解为二进制不进位加法来证明。 故我们只需检验 $A$ 中的每个基底而非 $\operatorname{span}(A)$ 即可判断这一位的值。 ## 0x04 定义 $A$ 的正交线性基为 $B$，使得对于所有 $x \in \operatorname{span}(A), y \in \operatorname{span}(B)$，满足 $\operatorname{popcount(x \& y)}$ 是偶数，且 $\operatorname{rank}(A) + \operatorname{rank}(B) = m$。 根据前面的引理，有 $$ B \cdot 2^{\operatorname{rank}(A)} = \operatorname{FWT} (A) \Leftrightarrow \operatorname{IFWT}(B \cdot 2^{\operatorname{rank}(A)}) = A $$ 一种简单的正交线性基构造方式是  用高斯消元整理关键位，旋转右上角到左下角得到。  证明可以考虑图中圈出矩形的左上角和右上角一定为 $1$，而两向量的异或的 $\operatorname{popcount}$ 为偶数，那么左下角和右上角的数要么全为 $0$，要么全为 $1$。 ## 0x05 知道了正交线性基怎么求，如何计算答案呢？ 考虑用 $\operatorname{FWT}$ 表示答案统计： $$ [z^c]P(A) = [z^0] (A * G^c) = [z^0] \operatorname{IFWT}(\operatorname{FWT}(F(A)) \cdot \operatorname{FWT}(G^c)) $$ 其中 $G^c$ 表示 $\sum_{x \geq 0} z^x [\operatorname{popcount}(x)=c]$。 其中： $$ [z^0] \operatorname{IFWT}(X) = 2^{-m} [z^0] \operatorname{FWT}(X) = 2^{-m} \sum_{i \geq 0} [z^i] X $$ 由于 $\operatorname{FWT}(F(A)) = F(B) \cdot 2^k$，而 $B$ 中的元素只有 $2^{\operatorname{rank}(B)} = 2^{m - \operatorname{rank}(A)}$ 个。故通过暴力得到 $P(B)$，即可通过组合数计算得 $P(A)$。 $$ [z^c]P(A) = 2^{k-m} \sum_{d \geq 0} [z^d] P(B) \sum_{i \geq 0} (-1)^i \binom d i \binom {m-d} {c-i} $$