CF2056F2 Xor of Median (Hard Version)
rlc202204
·
·
题解
题意：
定义一个序列是好的，当且仅当：
- 对于任意两个不同的 i,j 满足 i,j 都出现了至少一次，如果 i < j，则 i 的出现次数不多于 j 的出现次数。
求所有长度为 N，值域在 [0,m) 的好的整数序列的中位数的异或和。中位数定义为排序后第 \lfloor\frac{n+1}{2}\rfloor。
**题意：**
注意到这题求的是异或和，这意味着如果某个方案出现了偶数次相当于没有出现。
序列是否有序不影响好坏，但是计数的时候是有序的。
对于所有出现的数，不妨设出现次数是 $cnt_1,\dots,cnt_k$，方案数是：
$$
\binom{N}{cnt_1,cnt_2,\dots,cnt_k}
$$
如果这个东西是偶数，那么显然是不会计入答案的。
这是一个多项式系数，可以表示为若干个二项式系数的乘积，也就是组合数：
$$
\binom{N}{cnt_1}\binom{N-cnt_1}{cnt_2}\dots \binom{N - cnt_1-cnt_2-\dots,-cnt_{k-1}}{cnt_k}
$$
奇偶性相当于对 $2$ 取模，而组合数对小质数取模考虑 Lucas 定理。
如果最终是奇数，就要求 $cnt_1$ 在二进制每一位上都 $\le N$ 的每一位，$cnt_2$ 在二进制每一位上都 $\le N-cnt_1$ 的每一位，以此类推。
而注意到 $\sum_i cnt_i = N$，所以这个限制本质上就是 $cnt_1,cnt_2,\dots,cnt_k$ 构成了 $N$ 的所有 $=1$ 的二进制位的划分。那么显然出现次数最多的数严格大于一半，所以中位数就是出现次数最多，也就是最大的那个数。
这样就非常好做了，也成功理解了题目为什么给我们 $N$ 的二进制表示。不妨设 $n$ 表示 $N$ 的二进制下 $=1$ 的位置的个数，
先不管复杂度，我们考虑枚举 $0 \le k < m$，设计一个 dp：$f(i,j,x)$ 表示当前分完了前 $i$ 位，当前所有有 $j$ 个数，最小的一个是 $x$。
如果这一位是 $0$，则直接 $i \to i+1$ 复制过去，否则，有两种可能：
- $j$ 个数中某个数拿走，由于是二进制，所以不会影响大小关系。$f(i,j,x) \to j \times f(i+1,j,x)$。
- 新增一个 $< x$ 的数，$f(i,j,x) \to f(i+1,j,t)(t < x)$。
这样 dp 是 $O(nm^3)$，因为还要枚举 $k$，连 F1 都过不了。
但是注意到这很没必要，每个 $k$ 都要单独计算，所以我们把状态反过来定义，$f(i,j,x)$ 表示前 $i$ 位之后的都确定了，前 $i$ 位有 $j$ 个数，最小的是 $k$。
这样就变一次 $dp$ 即可统计答案，时间复杂度 $O(nm^2)$。可以过掉 F1。
但是 F2 的数据范围很大，我们上面的做法枚举了 $k$，这是 $O(m)$ 的，显然无法接受，我们考虑如何将这个 $k$ 融入到 dp 的贡献中。
注意到实际上 $j$ 的范围是 $n$ 而不是 $m$，这意味着实际上我们可以将 $k,j$ 相同的视作一种方案，最后乘上 $\binom{k}{j-1}$ 即可。
我们发现一个事：实际上 dp 的时候 $x$ 不影响转移系数，我们考虑化成两维：设 $f(i,j)$ 表示前 $i$ 位之后已经确定，前 $i$ 位有 $j$ 个数的总贡献是多少。
转移类似：
- 当 $j$ 是奇数的时候，可以 $f(i+1,j) \to f(i+1,j)$。
- 也可以 $f(i+1,j+1) \to f(i+1,j)$。
关键是如何设定初值？
注意到对于初始固定了要选 $j$ 个数的方案，$k$ 可行当且仅当 $\binom{k}{j-1}$ 是奇数，如果是奇数我们才计入贡献。
这样 dp 就是 $O(nm)$ 的了，但是依然和 $m$ 有关。
那么我们需要将初值和 dp 两部分分别优化。
观察这个 dp 的式子，我们发现从 $j$ 的变化是这样的：每一次 $j$ 是偶数只能变成 $j+1$，否则可以变成 $j,j+1$ 中的一个，最终会变成某个 $k$。
也就是 $n$ 长度的一个序列：$1,1,1,2,3,3,3,4,5,5,5,\dots$ 这样的。
注意到 $1 \sim k$ 一定至少出现一次，而奇数还可以多出现几次，设有 $t$ 个奇数，则相当于求解不定方程 $x_1+x_2+\dots+x_t = n - k$，这个可以组合数直接计算，注意到我们只关心奇偶性，所以可以直接拆位 $O(\log n)$ 计算。
所以如果我们能求出初值，我们也能求出最终的方案，$O(n)$ 枚举一共选了几个数即可。
现在我们考虑怎么求初值，相当于求 $0 \le t < m,\binom{t}{j-1}$ 为奇数的 $t$ 的异或和。我们注意到这就是要求 $t$ 的每一位都 $\ge j-1$ 的每一位，我们可以直接数位 dp，设 $f(i,0/1),g(i,0/1)$ 分别表示前 $i$ 位是否贴着上界的方案数和总贡献，转移的时候如果某一位填了 $1$ 并且前面的方案数是奇数就可以给贡献加上这一位。
这样我们就能在 $O(\log m)$ 的时间内计算出初值，从而在 $O(n \log m)$ 的时间内解决这个问题。
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int C(int n, int m) {//计算模 2 的余数
if (n < m)
return 0;
if (n == 0 || m == 0)
return 1;
for (int j = 20; j >= 0; j--)
if ((n >> j & 1) < (m >> j & 1))
return 0;
return 1;
}
int CC(int n, int m) {//总和为 n，m 个变量
return C(n + m - 1, m - 1);
}
const int k = 30;
int n, m;
int num[2][35] = {{0}};
int f[35][2] = {{0}};
int g[35][2] = {{0}};
void add(int &x, int y) {
x ^= y;
}
int cal(int t) {
for (int j = k; j >= 1; j--)
num[1][j] = (t >> (j - 1) & 1);
memset(f, 0, sizeof f), memset(g, 0, sizeof g);
f[0][0] = 1;
for (int j = 1; j <= k; j++) {
//转移 f[j][0]
if (f[j - 1][0])
add(g[j][0], (1 << (j - 1)));
if (num[1][j]) {
add(f[j][0], f[j - 1][0]);
add(g[j][0], g[j - 1][0]);
}
//转移f[j][1]
if (num[0][j]) {//一定可以填 1 并且一定贴上界
add(f[j][1], f[j - 1][1]);
add(g[j][1], g[j - 1][1]);
if (num[0][j] && f[j - 1][1])
add(g[j][1], (1 << (j - 1)));
if (!num[1][j]) {
add(f[j][1], f[j - 1][0]);
add(g[j][1], g[j - 1][0]);
}
}
else if (num[0][j] == num[1][j]) {
add(f[j][1], f[j - 1][1]);
add(g[j][1], g[j - 1][1]);//填 0
}
// cout << j << " ?? " << f[j][0] << " g:" << g[j][0] << " ?? f: " << f[j][1] << " g: " << g[j][1] << endl;
}
return g[k][1];
}
void slv() {
scanf("%d%d", &n, &m);
int t = 0;
for (int i = 0, x; i < n; i++)
scanf("%1d", &x), t += x;
for (int j = k; j >= 1; j--)
num[0][j] = (m >> (j - 1) & 1);
n = t;
int ans = 0;
for (int i = 1; i <= n; i++)
if (CC(n - i, (i + 1) / 2))
ans ^= cal(i - 1);//i - 1的所有贡献
printf("%d\n", ans);
}
int main() {
int T;
scanf("%d", &T);
while (T--)
slv();
return 0;
}
/*
1
2 3
10
*/
```