【题解】CF1770F Koxia and Sequence

有没有觉得其他题解的模二 Lucas 逆用太智慧了，有没有觉得这题的第一思路是直接拆位算每一位是否有贡献，而不是先满足和的限制列式？

这里提供另外一个做法。方向不同，结果一样。过程麻烦很多，但思路上套路一些。更适合我这种没脑子选手理解

CF 题目传送门 | 洛谷题目传送门 | 个人博客中查看

设 \(y\) 的位数为 \(m\)。

考虑 \(y\) 中的每个位 \(i\)（下文所有“位”都表示在 \(y\) 中有的），确定每个位上各有多少个 \(1\)，设第 \(i\) 位有 \(b_i\) 个 \(1\)；

列式子：\(ans=\oplus_{b_i>0} [\sum_i 2^i b_i=x] [\prod_i {n \choose b_i}\bmod 2]\oplus_i [b_i\bmod 2]2^i\)。

用 Lucas 定理在模二时的那个经典结论简化一下，得到：\(ans=\oplus_{b_i>0,b_i\subseteq n} [\sum_i 2^i b_i=x] \oplus_i [b_i\bmod 2]2^i\)

把后面的提出来，单独算一个位 \(k\) 对异或值有没有贡献，得到：\(ans=\oplus_k [\sum_{b_i>0,b_i\subseteq n} [\sum_i 2^i b_i=x]b_k \bmod 2]2^k\)

考虑里面的那部分：每个位可以被选若干次，但是选的次数是 \(n\) 的非空子集，且某一特定位 \(k\) 必须选奇数个，使它们的和为定值 \(x\) 的方案数（同时说明 \(n\) 若不是奇数则答案为 \(0\)）。

对于“\(n\) 的子集”的限制，考虑将 \(n\) 二进制拆分，如果第 \(i\) 位选的次数包含 \(n\) 的第 \(j\) 位，那么对总和有 \(2^{i+j}\) 的贡献。

所以把所有 \(2^{i+j}\) 拿出来，问题就变成：在里面选若干个，并且某一个必定选（即 \(2^{k+0}\)），并且保证所有 \(i\) 至少被选一次（非空），且和为 \(x\) 的方案数。

这个 \(i\) 至少被选一次很烦，枚举一个集合 \(s\) 表示 \(s\) 以外的位没有被选过，把这个限制在外面直接容斥掉。这样 \(i+j\) 相同的就可以视为没有区别的了。

对于必选的限制直接拿出来，那么问题转化为：有若干个 \(2\) 的次幂，值相同的不超过 \(m\) 个，选若干个使得和是 \(x-2^k\) 的方案数。

这个问题很平凡，直接从低往高枚举每个次幂选了多少个，数位 dp 即可，复杂度 \(O(m^3)\)，尝试优化也难以低于平方级别，不详细说了。

但是前面枚举位和容斥已经有 \(O(m2^m)\) 的复杂度，这个复杂度难以承受。

考虑其实只要求方案数的奇偶性，必然组成偶数方案数的分支都不必数，从这里入手优化。

对于一个 \(2^p\)，若它原本有 \(c_p\) 个，被选了 \(t_p\) 个，那么方案数的柿子就包含 \(c_p\choose t_p\)。

那么对于需要数的方案，对于每个 \(p\) 必然满足 \(t_p\subseteq c_p\)，那么类似于前面的步骤，我们可以直接对它二进制拆分，方案数不变。

（更严谨的一个理解：若 \(c_p\geq 2\)，钦定其中任意两个数为同一组，若只有一个被选择，则改为另一个被选择就得到了一个对应的合法方案，所以模 \(2\) 意义下只要算两个同时和同时不选的，等价于一个 \(2^{p+1}\)）

那么二进制拆分一下，从低到高枚举 \(p\) ，若 \(c_p\) 为奇数，则 \(c'_p=1\)，否则 \(c'_{p+1}=0\)，然后令 \(c_{p+1}\) 加上 \(\lfloor \frac{c_p}{2} \rfloor\)，最后得到的 \(c\) 对应的方案数奇偶性和原问题相同。

不难发现这就是直接进位，设最后得到的 \(c\) 数组对应的二进制数为 \(C\)，那么选出来的位的和必然是 \(C\) 的子集，即原问题方案数为奇数等价于 \(x-2^k \subseteq C\)。

同时不难发现 \(C\) 就是所有备选的 \(2^p\) 的和，即 \(C=sn-2^k\)，那么这个问题可以直接 \(O(1)\) 做了。

最后得到非常简洁的答案式：\(ans=\oplus_k [\sum_{k\in s,s\subseteq y} (-1)^{|y|-|s|} [x-2^k\subseteq sn-2^k] \bmod 2]2^k=\oplus_k [\sum_{k\in s,s\subseteq y} [x-2^k\subseteq sn-2^k] \bmod 2]2^k\)

复杂度 \(O(m2^m)\) 即 \(O(y\log_2 y)\)，代码显然不需要放。