Uoj#310. 【UNR #2】黎明前的巧克力

题意：给出一个可重集 （相等的两个元素视为不同元素），要求选出两个子集 ，满足 的异或和相等，且不选择相同元素。求方案数。

答案对 取模，，，时限 。

---

套路题。

异或和相同等价于异或和为 。

那么我们可以先找到一个子集 使得其异或和为 ，然后任意划分成 ，这构成一一对应。

每个元素都有两种可能的归宿，划分的方案数是 。

计算 其中多项式是集合幂级数，乘法是异或卷积。系数 是因为每个元素可以分到两个集合。

它的 项就是答案。

---

直接暴力卷积显然不优。注意到每个幂级数只有两个非 项，考虑如何快速得到最终的 变换结果。

设第 个幂级数为 ，我们要求的是 然后对 施加 ，取出 就是答案。

考虑 的可能取值。

在施加 变换时， 对每个位置的贡献都是 ，但是 的贡献可能是 也可能是 。 的可能取值是 或 。 总可以表示成 的形式。

记 ，即 中 出现的次数。

对 施加 变换，我们能够得到每个位置上 的和（而非乘积）。

设位置 上 有 个，而 有 个，能得到 解这个方程就能得到 ，然后快速幂（或光速幂）计算 。

注意最后要减去空集的贡献。

复杂度 。