CF1770F Koxia and Sequence
这题，太牛逼了。
- 第一步，根据对称性，
a_i = t 的序列数量相等，所以n 为偶数时答案为0 ，n 为奇数时答案为所有a_1 的异或和。 - 第二步，拆位，对每个
i 计算a_1 第i 位为1 的方案数。这一步比较平凡。以下将a_1 减去2 ^ i 。
接下来有两个方向：
一是继续把每一位的贡献拆开来，这样比较容易满足按位或为
二是直接考虑
对第一个方向进行每一位的贡献系数不大于
-
第三步，容斥，设
f(y) 表示按位或为y 的子集的方案数，则按位或恰为y 的方案数为\sum\limits_{y'\subseteq y} (-1) ^ {|y| - |y'|} f(y') 。因为只关心奇偶性，故可进一步写为\bigoplus\limits_{y'\subseteq y} f(y') 。接下来着眼于每个y' 。 -
第四步，也是最牛逼的一步，即逆用组合数奇偶性公式，你不是要
[a_i\subseteq y'] 嘛，我直接写成\binom {y'} {a_i} \bmod 2 。 -
第五步，根据范德蒙德卷积化简公式：
\begin{aligned} \mathrm{ans} & = \bigoplus\limits_{\sum a_i = x - 2 ^ i} [a_1\subseteq (y' - 2 ^ i)] [a_2\subseteq y'] \cdots [a_n\subseteq y'] \\ & = \left(\sum\limits_{\sum a_i = x - 2 ^ i} \binom {y' - 2 ^ i} {a_1} \binom {y'} {a_2} \cdots \binom {y'} {a_n}\right)\bmod 2 \\ & = \binom {ny' - 2 ^ i} {x - 2 ^ i}\bmod 2 \\ & = [(x - 2 ^ i) \subseteq (ny' - 2 ^ i)] \end{aligned}
对每个