题解：P17875 [FJCPC 2026] 蛇小弟与奶龙
Li2021
·
·
题解
设值域是 [0,2^V)。考虑把限制写成代数式的形式。设全集 U=\{1,2,\dots,n\}，c_i=a_i\oplus b_i，则有
\begin{aligned}
& [c_1\oplus c_2\oplus \dots\oplus c_n=0] \\
= & \frac{1}{2^V}\sum_{S\subseteq U} (-1)^{|S\cap(c_1\oplus c_2\oplus\dots\oplus c_n)|} \\
= & \frac{1}{2^V}\sum_{S\subseteq U}\prod_{i=1}^{n}(-1)^{|S\cap c_i|}
\end{aligned}
其实本质上还是对 c_i 做了 FWT，即 \prod x^{c_i}=1，不过把 FWT 的定义搬过来了。
于是答案即 \frac{1}{2^V}\sum\limits_{c\ \text{legal}}\sum\limits_S\prod\limits_{i=1}^{n}(-1)^{|S\cap c_i|}=\frac{1}{2^V}\sum\limits_S\prod\limits_{i=1}^{n}\sum\limits_{c_i\ \text{legal}}(-1)^{|S\cap c_i|}。
分析一下 c_i 合法的情况，这等价于 a_i\oplus c_i\le a_i，也即 c_i 的最高位为 a_i 的其中一位，或者 c_i=0，形如：
a[i]: ....1...1....1
c[i]: 0..01[01]*
or 0.......1[01]*
or 0............1
or 0............0
于是 \sum\limits_{c_i\ \text{legal}}(-1)^{|S\cap c_i|}=1+\sum\limits_{j=0}^{V-1}[j\in a_i](-1)^{[j\in S]}2^j[S_{<j}=\varnothing]，其中 S_{<j} 表示 S 中所有 <j 的元素。
则答案式
\begin{aligned}
\text{Ans} = & \frac{1}{2^V}\sum_S\prod_{i=1}^{n}\left(1+\sum_{j=0}^{V-1}[j\in a_i](-1)^{[j\in S]}2^j[S_{<j}=\varnothing]\right) \\
= & \frac{1}{2^V}\sum_S\prod_{i=1}^{n}\left(1+\sum_{j=0}^{\text{lb}(S)-1}[j\in a_i]2^j-[\text{lb}(S)\in a_i]2^{\text{lb}(S)}\right) \\
= & \frac{1}{2^V}\sum_{k=0}^{V-1}2^{V-k-1}\prod_{i=1}^{n}\left(1+\sum_{j=0}^{k-1}[j\in a_i]2^j-[k\in a_i]2^k\right)
\end{aligned}
第二步是因为求和式只与 \text{lb}(S) 有关，\text{lb}(S) 为 S 的 lowbit。注意上式未考虑 S=\varnothing 的情况，需单独处理，只需将答案加上 \frac{1}{2^V}\prod(1+a_i)。
因此可以通过前缀和预处理 \sum\limits_{j=0}^{k-1}[j\in a_i]2^j 在 O(nV) 时间复杂度内解决。