专栏文章

题解：CF2056F2 Xor of Median (Hard Version)

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miniyrw7
此快照首次捕获于
2025/12/02 03:11
3 个月前
此快照最后确认于
2025/12/02 03:11
3 个月前
查看原文

引理

若 aa 的二进制上 11 的位置集合是 bb 的子集，则记作 a⊂ba \subset b。所有变量都是整数。
引理 1：(nm){n \choose m} 为奇数，当且仅当 m⊂nm \subset n。
引理 2：{nm}{n \brace m} 为奇数，当且仅当 (n−m)and⁡⌊m−12⌋=0(n-m) \operatorname{and} \lfloor \frac{m-1}{2} \rfloor = 0。（and⁡\operatorname{and} 为按位与）。
引理 3：(nm1,m2,…mp){n \choose {m_1, m_2, \dots m_p}} 为奇数，当前仅当 m1,m2,…mpm_1, m_2, \dots m_p 是 nn 的二进制划分。即 m1or⁡m2or⁡…or⁡mp=nm_1 \operatorname{or} m_2 \operatorname{or} \dots \operatorname{or} m_p = n，miand⁡mj=0(1≤i,j≤p)m_i \operatorname{and} m_j = 0 (1\le i,j\le p)
引理 4：⨁i=04x+yi={4x,y=01,y=14k+3,y=20,y=3\bigoplus_{i=0}^{4x+y} i = \begin{cases} 4x, y=0 \\ 1, y=1 \\ 4k+3, y=2 \\ 0, y=3 \end{cases}
此处只证明引理 3。首先 (nm1){n \choose m_1} 要是奇数，所以 m1⊂nm_1 \subset n，然后 (n−m1m2){n-m_1 \choose m_2} 也要是奇数，所以 nn 去掉 m1m_1 的部分要包含 m2m_2。以此类推，nn 就是 m1,m2,…mpm_1, m_2, \dots m_p 的二进制划分。

F1 题解

首先，可以枚举 cnt\text{cnt} 数组，考虑对答案的贡献。由引理 3，若一种 cnt\text{cnt} 想对答案产生贡献，必须是 nn 的二进制划分。此时最大的 cnt\text{cnt} 一定超过总和的一半，所以中位数就是最大值。
记 nn 中 11 的位置数为 bb，枚举 cnt\text{cnt} 数组不为零的位置数 pp、原数组 aa 的最大值 xx，答案为：
⨁x=0m−1⨁p=1min(b,m)(({bp}(xp−1) mod 2)x)\bigoplus_{x=0}^{m-1} \bigoplus_{p=1}^{min(b,m)} \left ( \left ( {b \brace p} {x \choose p-1} \bmod 2 \right ) x \right )
这里简单解释一下，首先 bb 个二进制位要分成 pp 份后排序，这里的方案数就是第二类斯特林数，然后原数组要从 [0,x)[0,x) 中选 p−1p-1 种数（xx 已经是最大值了）。
这样 F1 就做完了，使用引理 1、引理 2 计算，时间复杂度 O(km)O(km)。
CPP
#include<bits/stdc++.h>
using namespace std;
int t,k,n,m,ans;
char n2[200005];
int main() {
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d%s",&k,&m,n2);
		n=0;
		for(int i=0; i<k; i++) n+=(n2[i]=='1');
		ans=0;
		for(int y=1; y<=min(n,m); y++)
			for(int x=0; x<m; x++)
				if(((y-1)|x)==x && ((n-y)&((y-1)/2))==0)
					ans^=x;
		printf("%d\n",ans);
	}
	return 0;
}

F2 题解

记：
f(x)=⨁p=1min(b,m){bp}(xp−1) mod 2=⨁0≤y<min(b,m),y⊂x{by+1} mod 2f(x) = \bigoplus_{p=1}^{min(b,m)} {b \brace p} {x \choose p-1} \bmod 2 = \bigoplus_{0 \le y <min(b,m), y \subset x} {b \brace y+1}\bmod 2
答案就是 ⨁x=0m−1f(x)x\bigoplus_{x=0}^{m-1} f(x) x。
我们分成两个部分进行优化，第一部分是计算 f(x)f(x)，第二部分是快速求异或和。
第一部分的可以使用 sosdp。
注意到 xx 的高位均没有用。形式化地，令 NN 是最小的满足 2N>min(n,m)2^N > min(n,m) 的数，f(x)=f(x mod 2N)f(x) = f(x \bmod 2^N)。因此只需要处理 [0,2N)[0, 2^N) 部分的 f(x)f(x) 就行了，这一部分时间复杂度 O(klog⁡k)O(k \log k)。
第二部分，由引理 4 可以简单计算。
CPP
#include<bits/stdc++.h>
using namespace std;
int t,k,n,m,N,ans;
char n2[200005];
int f[300005];
int main() {
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d%s",&k,&m,n2);
		n=0;
		for(int i=0; i<k; i++) n+=(n2[i]=='1');
		ans=0;
		int N=0;
		while((1<<N)<=min(n,m)) N++;
		for(int j=0; j<(1<<N); j++) f[j]=(j<n && j<m && (((n-j-1)&(j/2))==0));
		for(int i=0; i<N; i++)
			for(int j=0; j<(1<<N); j++)
				if(j&(1<<i))
					f[j]^=f[j^(1<<i)];
		// 分块计算
		int t=0, cnt=0;
		for(int x=0; x<(1<<N); x++)
			if(f[x])
				t^=x, cnt++;
		int x=0, bk=m>>N;
		if(bk&1) ans^=t;
		if(cnt&1) {
			// 0 xor 1 xor 2 xor ... xor bk-1
			switch((bk-1)&3) {
				case 0: {
					ans^=((bk-1)>>2<<2)<<N;
					break;
				}
				case 1: {
					ans^=1<<N;
					break;
				}
				case 2: {
					ans^=(((bk-1)>>2<<2)+3)<<N;
					break;
				}
			}
		}
		for(int x=((m>>N)<<N); x<m; x++) ans^=x*f[x%(1<<N)];
		printf("%d\n",ans);
	}
	return 0;
}

评论

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

正在加载评论...