memset0's Notebook

有没有可爱的小哥哥来我的博客玩玩呀~

题解 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} $$


2020-04-26 23:52:04 in 题解