专栏文章

CF2056F2 Xor of Median (Hard Version)

rrlc202204
CF2056F2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqd31z2
此快照首次捕获于
2025/12/04 02:49
3 个月前
此快照最后确认于
2025/12/04 02:49
3 个月前
查看原文
题意：
定义一个序列是好的，当且仅当：
  • 对于任意两个不同的 i,ji,j 满足 i,ji,j 都出现了至少一次，如果 i<ji < j，则 ii 的出现次数不多于 jj 的出现次数。
求所有长度为 NN，值域在 [0,m)[0,m) 的好的整数序列的中位数的异或和。中位数定义为排序后第 ⌊n+12⌋\lfloor\frac{n+1}{2}\rfloor。
NN 以二进制形式给出，log⁡2N≤2×105,m≤109\log_2 N \le 2 \times 10^5,m \le 10^9。
题意：
注意到这题求的是异或和，这意味着如果某个方案出现了偶数次相当于没有出现。
序列是否有序不影响好坏，但是计数的时候是有序的。
对于所有出现的数，不妨设出现次数是 cnt1,…,cntkcnt_1,\dots,cnt_k，方案数是：
(Ncnt1,cnt2,…,cntk)\binom{N}{cnt_1,cnt_2,\dots,cnt_k}
如果这个东西是偶数，那么显然是不会计入答案的。
这是一个多项式系数，可以表示为若干个二项式系数的乘积，也就是组合数：
(Ncnt1)(N−cnt1cnt2)…(N−cnt1−cnt2−…,−cntk−1cntk)\binom{N}{cnt_1}\binom{N-cnt_1}{cnt_2}\dots \binom{N - cnt_1-cnt_2-\dots,-cnt_{k-1}}{cnt_k}
奇偶性相当于对 22 取模，而组合数对小质数取模考虑 Lucas 定理。
如果最终是奇数，就要求 cnt1cnt_1 在二进制每一位上都 ≤N\le N 的每一位，cnt2cnt_2 在二进制每一位上都 ≤N−cnt1\le N-cnt_1 的每一位，以此类推。
而注意到 ∑icnti=N\sum_i cnt_i = N，所以这个限制本质上就是 cnt1,cnt2,…,cntkcnt_1,cnt_2,\dots,cnt_k 构成了 NN 的所有 =1=1 的二进制位的划分。那么显然出现次数最多的数严格大于一半，所以中位数就是出现次数最多，也就是最大的那个数。
这样就非常好做了，也成功理解了题目为什么给我们 NN 的二进制表示。不妨设 nn 表示 NN 的二进制下 =1=1 的位置的个数，
先不管复杂度，我们考虑枚举 0≤k<m0 \le k < m，设计一个 dp：f(i,j,x)f(i,j,x) 表示当前分完了前 ii 位，当前所有有 jj 个数，最小的一个是 xx。
如果这一位是 00，则直接 i→i+1i \to i+1 复制过去，否则，有两种可能：
  • jj 个数中某个数拿走，由于是二进制，所以不会影响大小关系。f(i,j,x)→j×f(i+1,j,x)f(i,j,x) \to j \times f(i+1,j,x)。
  • 新增一个 <x< x 的数，f(i,j,x)→f(i+1,j,t)(t<x)f(i,j,x) \to f(i+1,j,t)(t < x)。
这样 dp 是 O(nm3)O(nm^3)，因为还要枚举 kk，连 F1 都过不了。
但是注意到这很没必要，每个 kk 都要单独计算，所以我们把状态反过来定义，f(i,j,x)f(i,j,x) 表示前 ii 位之后的都确定了，前 ii 位有 jj 个数，最小的是 kk。
这样就变一次 dpdp 即可统计答案，时间复杂度 O(nm2)O(nm^2)。可以过掉 F1。
但是 F2 的数据范围很大，我们上面的做法枚举了 kk，这是 O(m)O(m) 的，显然无法接受，我们考虑如何将这个 kk 融入到 dp 的贡献中。
注意到实际上 jj 的范围是 nn 而不是 mm，这意味着实际上我们可以将 k,jk,j 相同的视作一种方案，最后乘上 (kj−1)\binom{k}{j-1} 即可。
我们发现一个事：实际上 dp 的时候 xx 不影响转移系数，我们考虑化成两维：设 f(i,j)f(i,j) 表示前 ii 位之后已经确定，前 ii 位有 jj 个数的总贡献是多少。
转移类似：
  • 当 jj 是奇数的时候，可以 f(i+1,j)→f(i+1,j)f(i+1,j) \to f(i+1,j)。
  • 也可以 f(i+1,j+1)→f(i+1,j)f(i+1,j+1) \to f(i+1,j)。
关键是如何设定初值？
注意到对于初始固定了要选 jj 个数的方案，kk 可行当且仅当 (kj−1)\binom{k}{j-1} 是奇数，如果是奇数我们才计入贡献。
这样 dp 就是 O(nm)O(nm) 的了，但是依然和 mm 有关。
那么我们需要将初值和 dp 两部分分别优化。
观察这个 dp 的式子，我们发现从 jj 的变化是这样的：每一次 jj 是偶数只能变成 j+1j+1，否则可以变成 j,j+1j,j+1 中的一个，最终会变成某个 kk。
也就是 nn 长度的一个序列：1,1,1,2,3,3,3,4,5,5,5,…1,1,1,2,3,3,3,4,5,5,5,\dots 这样的。
注意到 1∼k1 \sim k 一定至少出现一次，而奇数还可以多出现几次，设有 tt 个奇数，则相当于求解不定方程 x1+x2+⋯+xt=n−kx_1+x_2+\dots+x_t = n - k，这个可以组合数直接计算，注意到我们只关心奇偶性，所以可以直接拆位 O(log⁡n)O(\log n) 计算。
所以如果我们能求出初值，我们也能求出最终的方案，O(n)O(n) 枚举一共选了几个数即可。
现在我们考虑怎么求初值，相当于求 0≤t<m,(tj−1)0 \le t < m,\binom{t}{j-1} 为奇数的 tt 的异或和。我们注意到这就是要求 tt 的每一位都 ≥j−1\ge j-1 的每一位，我们可以直接数位 dp，设 f(i,0/1),g(i,0/1)f(i,0/1),g(i,0/1) 分别表示前 ii 位是否贴着上界的方案数和总贡献，转移的时候如果某一位填了 11 并且前面的方案数是奇数就可以给贡献加上这一位。
这样我们就能在 O(log⁡m)O(\log m) 的时间内计算出初值，从而在 O(nlog⁡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
*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...