CF2056F2 题解

· · 题解

困难 *3000。

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

考虑如何通过 F1。

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

\begin{aligned}\dbinom{n}{c_0,c_1,\cdots,c_{m-1}}\operatorname{mod}2\end{aligned}

由卢卡斯定理的经典结论，设 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}。

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

\begin{aligned}\bigoplus_{y=1}^{\min(m,|S|)}\end{aligned}\bigoplus_{x=0}^{m-1}\left[\dbinom{x}{y-1}\begin{Bmatrix}|S|\\y\end{Bmatrix}\operatorname{mod} 2\right]\times x

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

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

$\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 中的式子可以进一步化简为 $$\begin{aligned}\bigoplus_{x=0}^{m-1}x\times \left[\left(\bigoplus_{y\subset x}f(y)\right)\operatorname{mod} 2\right]\end{aligned}$$ 这里的 包含符号 是二进制意义下的。 看上去还是要枚举 $x$，但实际上由于 $y$ 很小，设 $r=\log |S|$，后面那个求和式子的值只跟 $x$ 的后 $r$ 位有关。枚举这些位，发现我们要算一个 $0\oplus 1\oplus 2\cdots \oplus w$ 的形式，这是容易的，分类讨论一下就行。 子集的 $f$ 之和显然可以高维前缀和。 至此我们以 $O(k\log k)$ 的复杂度解决了 F2。[F2 submission](https://codeforces.com/contest/2056/submission/303870014)。