专栏文章

题解：AT_abc150_f [ABC150F] Xor Shift

JJHR100330
AT_abc150_f题解参与者 1已保存评论 0

文章操作

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

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

题目大意

将 aa 序列前 kk 个数放到最后，使得 a1⊕b1=a2⊕b2=⋯=an⊕bn=xa_1 \oplus b_1 = a_2 \oplus b_2 = \cdots = a_n \oplus b_n = x，求满足条件的所有 kk 和 xx。

思路

首先有一个显然的 O(n2)O(n^2) 暴力，走不下去，考虑其他做法。
异或运算是基于二进制位的，所以往二进制的方向考虑，即要保证所有 ai⊕bia_i \oplus b_i 的每一个二进制位相等。
记 Sn,jS_{n,j} 为 nn 在二进制下 2j2^j 的系数，由于 1⊕1=0⊕0=01 \oplus 1 = 0 \oplus 0 = 0，1⊕0=0⊕1=11 \oplus 0 = 0 \oplus 1 = 1。
即要么 Sai,jS_{a_i,j} 与 Sbi,jS_{b_i,j} 均相等，此时 Sai⊕bi,j=Sx,j=0S_{a_i \oplus b_i,j} = S_{x,j} = 0。
要么 Sai,jS_{a_i,j} 与 Sbi,jS_{b_i,j} 均不等，此时 Sai⊕bi,j=Sx,j=1S_{a_i \oplus b_i,j} = S_{x,j} = 1。
此时就可以枚举 jj，将所有 Sbi,jS_{b_i,j} 和 Sbi,j⊕1S_{b_i,j} \oplus 1 哈希，再将所有 Sai,jS_{a_i,j} 哈希滚动对比。
如果有一个二进制位无法满足条件，则此时的 kk 就不满足条件，标记即可，最后没被标记的 kk 就符合条件。
最后由于 ai⊕bia_i \oplus b_i 均等于 xx，计算其中一组 aia_i 和 bib_i 的异或值即可。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned ll

const int N = 200050, base = 131; // 本题没有卡自然溢出哈希

int n;
int a[N], b[N], ans[N];
ull p[N] = {1}, h, H, ha[N];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++)
		p[i] = p[i - 1] * base;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	for(int i = 1; i <= n; i ++)
		cin >> b[i];
	for(int u = 0; u <= 29; u ++){
		int mask = 1 << u;
		h = H = 0;
        // 将 S_{b_i,u} 和 S_{b_i,u} ^ 1 哈希
		for(int i = 1; i <= n; i ++){
			h = h * base + !!(b[i] & mask);
			H = H * base + !(b[i] & mask);
		}
        // 将 S_{a_i,u} 哈希
		for(int i = 1; i <= n; i ++)
			ha[i] = ha[i - 1] * base + !!(a[i] & mask);
		for(int i = 0; i < n; i ++)
			if((ha[n] - ha[i] * p[n - i]) * p[i] + ha[i] != h && (ha[n] - ha[i] * p[n - i]) * p[i] + ha[i] != H)
				ans[i] = 1;
	}
	for(int i = 0; i < n; i ++)
		if(ans[i] == 0)
			cout << i << " " << (a[n] ^ b[n - i]) << endl;
	return 0;
}

评论

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

正在加载评论...