题解：CF2056F1 Xor of Median (Easy Version)

· · 题解

CF2056F1 Xor of Median (Easy Version)

*2700，有点难的数数题。

定义母序列为一个单调不降的好序列。

考虑先确定一个长度为 n 的母序列 a，其有 k 个不同的数且这些数被编号为 1\sim k，在统计答案时再将这 k 个编号映射到原来的 m 种数（注意这里的 k 和题目描述中的 k 不同）。下文中的 c_i 表示对于这个序列 a，数 i 出现的次数。

通过组合数常识，我们可以得到上面的母序列 a 所能生成的好序列数量：

\prod_{i=1}^{k}\binom{n-\sum_{j=1}^{i-1}c_j}{c_i}

考虑到异或的特殊性，一个母序列只会在其生成的好序列数量为奇数的时候会产生贡献。所以我们相当于要得到上述式子对 2 取模的结果。

根据 Lucas 定理的推论，\binom{x}{y}\equiv1\pmod{2} 当且仅当 x\And y=y。所以说对于任意 1\le i\le k，都有 n-\sum_{j=1}^{i-1}c_i\And c_i=c_i。

继续分析。我们注意到对于 c_1 来说，如果满足 n\And c_1=c_1，那么 n-c_1 这个减法操作在二进制中是不会退位的。而这也就代表着减去 c_1 后得到的 n^{'} 的二进制表示是不会产生额外的为 1 的位置，且在 c_1 二进制表示中为 1 的位置现在一定为 0。此时如果 c_2\And c_1\neq 0，那么 n-c_1\And c_2 一定不等于 c_2，因为 c_2 与 c_1 共同拥有的那个二进制位现在一定为 0。因此我们可以得到 c_1\And c_2=0。通过这种方式类似的归纳一下就可以得到，对于任意 1\le i,j\le k,i\neq j， 都有 c_i\And c_j=0。

有了这个结论之后，又根据 \sum_{i=1}^{k}c_i=n 和 c_1\le c_2\le \cdots\le c_k 这两条限制，我们可以得到关于 c 的信息：

  1. c_1\lor c_2\lor\cdots\lor c_k=n
  2. \forall 1\le i<k,\text{highbit}(c_i)<\text{highbit}(c_{i+1})

其中 \text{highbit}(x) 表示 x 的二进制表示中最高位的值。

由于 c_k 是最大值，所以我们可以得到 \text{highbit}(c_k)=\text{highbit}(n)。又因为不同的 c_i 之间两两无交，所以说 \sum_{i=1}^{k-1}c_i< 2^{len}（其中 len 是 n 的二进制表示长度）。而 c_k\geq 2^{len}，所以说 \sum_{i=1}^{k-1}c_i<c_k。根据中位数的定义，我们可以发现这个序列的中位数一定为 k。

设 n 的二进制表示中一共有 s 个位置为 1。考虑枚举我们这个母序列中不同数的种类 k，那么我们计数 c 的数量就相当于把每个为 1 的位置分配到一个盒子里去，其方案数就是第二类斯特林数。再枚举最大值映射到的数 x，那么 x 被异或的次数就是 \sum_{k=1}^{s}\dbinom{x}{k-1}\begin{Bmatrix}s\\k\end{Bmatrix}。直接暴力预处理第二类斯特林数，时间复杂度 \operatorname{O}(k^2+mk)

code