题解：CF2056F1 Xor of Median (Easy Version)

· · 题解

很厉害的题，评个紫不过分吧。虽然是我自己推出来的，但是花了一个小时，场上基本不可能过。

首先我们注意到题目要求的是中位数的异或和，感性理解一下可以发现很多方案中的中位数相互抵消了。假设我们有一种方案选取了 k 种数字，从小到大分别选取了 a_1,a_2,\dots,a_k 个，那么对应序列的方案应为：

\frac {n!} {\prod_{i=1}^k a_i!}

这是可重集排列的方案数，因为我们是异或，所以上述式子只有为奇数时才有贡献。定义函数 f(n) 表示 n! 中 2 的次幂，也就是 2^{f(n)}||n!，上述式子在 \bmod 2 意义下等价 f(n)=\sum_{i=1}^k f(a_i)，形式化表述：

\frac {n!} {\prod_{i=1}^k a_i!} \equiv [f(n)=\sum_{i=1}^k f(a_i)] \pmod 2

所以其实对于 n，我们只用统计 f(n)=\sum_{i=1}^k f(a_i) 所有方案的中位数异或和。

那么什么样的 a 序列满足上述条件呢？打个表发现，a 序列是 n 二进制位的一个拆分。形式化的说，我们应该统计满足如下性质的 a 序列：

对于任意的 i,j，都满足 a_i \operatorname{and} a_j=0

并且 \sum_{j=1}^k a_j=n

这个证明不难，结论也很直观。

我们惊奇的发现，设 n 的最高位是 2^K，因为 2^K>\frac n 2，所以在这个序列中中位数就是最大值。

那么这个就简单了，我们枚举 k，设 n 的二进制位中有 cnt 个 1，那么方案数就是 cnt \brace k，也就是将 cnt 个 1 分配到 k 个集合中，且集合不为空的方案数。

同时，我们再枚举最大值 x，选取数字的方案显然就是 {{cnt} \brace {k}} {x \choose k-1}，当这个值是奇数的时候，我们就可以异或上 x，总复杂度是 O(nk)。