题解：CF2056F1 Xor of Median (Easy Version)

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

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

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

所以其实对于 $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)$。