CF2056F2 题解

困难 *3000。

用 $c$ 代替题面中的 $\text{cnt}$，因为不想打 \text{}。

考虑如何通过 F1。

注意到题目要求的是异或，而在 $c$ 数组确定时中位数 $x$ 也是确定的。因此我们要考虑的，就是对于一个指定的 $c$ 数组，有多少个合法的原数组，并且只需要考虑这个值的奇偶性。而这个值显然就是多重集全排列，即

由卢卡斯定理的经典结论，设 $n$ 中为 $1$ 的二进制位的集合是 $S$，则这个式子为 $1$ 当且仅当 $c_0,c_1,\cdots,c_{m-1}$ 不重不漏的划分了 $S$。即，$S$ 中每一位都恰属于一个 $c_i$。

考虑最大的 $c$，设为 $c_x$。则一定有 $2c_x\ge n$，因为 $c_x$ 包含了 $n$ 的最高位。那么中位数其实就是 $x$。

由于 F1 中 $m,k$ 较小，可以枚举一些东西。尝试枚举非零元的数量 $y$，那么划分 $S$ 的方案数直接可以用斯特林数计算。然后就是把划分出来的数按大小关系填进 $c$ 里面去，显然只需选位置就行，又因为最大值在 $x$ 处，因此这部分方案数就是 $\dbinom{x}{y-1}$。

到这里可以得到最终答案表达式：

直接实现上式就是 $O(km)$ 的，可以通过 F1。

继续做的话首先需要前置知识：

$\dbinom{n}{m}$ 为奇数等价与 $n\operatorname{and} m=m$。

$\begin{Bmatrix}n\\m\end{Bmatrix}$ 为奇数等价于 $(n-m)\operatorname{and} {\lfloor\frac{m-1}{2}\rfloor}=0$。

（前者是卢卡斯定理，后者可以考虑递推公式中 $m$ 的奇偶性证明。）

考虑继续优化。发现如果对某个特定的 $x$，能快速找出对应的 $y$ 的贡献总和就很好。利用上述结论可知，设 $f(y)=\begin{Bmatrix}|S|\\y+1\end{Bmatrix}\operatorname{mod} 2$，则 F1 中的式子可以进一步化简为

这里的 包含符号 是二进制意义下的。

看上去还是要枚举 $x$，但实际上由于 $y$ 很小，设 $r=\log |S|$，后面那个求和式子的值只跟 $x$ 的后 $r$ 位有关。枚举这些位，发现我们要算一个 $0\oplus 1\oplus 2\cdots \oplus w$ 的形式，这是容易的，分类讨论一下就行。

子集的 $f$ 之和显然可以高维前缀和。

至此我们以 $O(k\log k)$ 的复杂度解决了 F2。F2 submission。