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

$1 \leq n \leq 2 \times 10^5,\ 0 \leq m \leq 53$。

## 0x01

• $\operatorname{popcount}(x)$ 表示 $x$ 的二进制表示下 $1$ 的个数
• $\langle i, j \rangle = \operatorname{popcount(i \& j)}$

• $\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$ 为由题中给定数得到的线性基

## 0x02

$$(z^x) * F(A) = F(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}

## 0x03

\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}

$\langle x,y \rangle$ 和 $\oplus$ 运算满足结合律：

$$\langle i,x \rangle \oplus \langle j,x \rangle = \langle i \oplus j, x \rangle$$

## 0x04

$$B \cdot 2^{\operatorname{rank}(A)} = \operatorname{FWT} (A) \Leftrightarrow \operatorname{IFWT}(B \cdot 2^{\operatorname{rank}(A)}) = A$$

## 0x05

$$[z^c]P(A) = [z^0] (A * G^c) = [z^0] \operatorname{IFWT}(\operatorname{FWT}(F(A)) \cdot \operatorname{FWT}(G^c))$$

$$[z^0] \operatorname{IFWT}(X) = 2^{-m} [z^0] \operatorname{FWT}(X) = 2^{-m} \sum_{i \geq 0} [z^i] X$$

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