题解：CF2056F1 Xor of Median (Easy Version)

· · 题解

一道好题。

首先，注意到题目所求的是所有中位数的异或。而中位数的范围又在 [0,m) 之内。只有当只有奇数个序列中位数为 i，答案才会异或上 i。 所以考虑枚举每一个中位数，来计算答案。

根据排列组合的公式，共有 \frac{n!}{\prod_{i=0}^{m - 1}cnt_i!} 种序列对应 cnt，若 \frac{n!}{\prod_{i=0}^{m - 1}cnt_i!} 为偶数，则这个序列的中位数不会算入答案。因为一个数被异或了偶数次。所以若 cnt 要被算入答案中，则分式上下的 2 的次幂必须一样。

定义 f(i) 为 i! 中 2 的次幂。则能被算入答案的 cnt 一定得满足 f(n) = \sum_{i=0}^{m - 1}cnt_i。易得只有当 \sum_{i=0}^{m - 1}cnt_i=n 且 cnt 中任意两个数按位与的值为 0。换句话说，cnt 是 n 的一个二进制拆分。举个例子，n=7 时，对应的 cnt 可以为 1,6，也可以为 1,2,4 等等。

因为题目中要求序列的 cnt 除 0 以外的元素必须得递增，所以 cnt 中最大的元素一定是 cnt 中非 0 的最靠后的元素。又因为 cnt 是 n 的一个二进制拆分，所以 \max\{cnt\} 一定包含二进制中 n 的最高位。所以 \max\{cnt\} 一定大于 n / 2。所以每个满足要求的序列的中位数只能是序列最大的元素。

所以，我们先枚举 k 为序列中的元素个数。设 cnt 为 n 二进制中一的个数。共有 S(cnt, k) 中方案。也就是将 cnt 个进制位分配给 k 个位置，位置无序的方案数。然后我们还需要枚举这些数放在哪个位置。设最大的数为 i，则方案数为 C^{k - 1}_{x}。总的方案数为 S(cnt, k)C^{k - 1}_{x}。只要其为奇数，就在答案中异或上 x。

复杂度 O(nk)。