AtCoder Beginner Contest 150 F. Xor Shift （异或性质+扩展kmp）

题目

给两个长为n(n<=2e5)的序列a和b，

你可以自行选择一个k(0<=k<n)和一个x(x>=0)，

构造新序列，其中为异或

使得c序列和b序列完全相等，

输出所有合法的(k,x)

思路来源

https://www.luogu.com.cn/problem/solution/AT_abc150_f

题解

考虑n=3时的两个序列，

a[0] a[1] a[2]

b[0] b[1] b[2]

不妨假设k=1时，能找到对应的x使式子成立，有：

相邻项两两异或，有

也就是，只要存在某个循环偏移量k，

使得a的相邻项异或值，和b的相邻项异或值，逐项相等

总能找到x，使得(k,x)合法，

代入（1）式中，显然有

所以，对相邻项异或，构造两个新序列s1和s2，

问题转化成，对于s1的循环串，有多少个是和s2完全相同的

将s1扩展成原来的2倍之后（s1=s1+s1），与s2做扩展kmp即可

代码

// Problem: F - Xor Shift
// Contest: AtCoder - AtCoder Beginner Contest 150
// URL: https://atcoder.jp/contests/abc150/tasks/abc150_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
const int N=2e5+10,M=4e5+10;
int n,a[N],b[N],net[N],ex[N],s1[M],s2[N];
vector<P>ans;
void extkmppre(int s[],int len){
	int i=0,j,pos;
	net[0]=len;
	while(i+1<len&&s[i]==s[i+1])i++;
	net[1]=i,pos=1;
	rep(i,2,len-1){
		if(net[i-pos]+i<net[pos]+pos){
			net[i]=net[i-pos];
		}
		else{
			j=net[pos]+pos-i;
			if(j<0)j=0;
			while(i+j<len&&s[j]==s[i+j])j++;
			net[i]=j,pos=i;
		}
	}
}
void extkmp(int s1[],int s2[],int l1,int l2){
	int i=0,j,pos;
	extkmppre(s2,l2);
	while(i<l2&&i<l1&&s1[i]==s2[i])i++;
	ex[0]=i,pos=0;
	if(ex[0]==l2)ans.pb(P(0,a[0]^b[0]));
	rep(i,1,l1-1){
		if(net[i-pos]+i<ex[pos]+pos){
			ex[i]=net[i-pos];
		}
		else{
			j=ex[pos]+pos-i;
			if(j<0)j=0;
			while(i+j<l1&&j<l2&&s1[i+j]==s2[j])j++;
			ex[i]=j,pos=i;	
		}
		if(ex[i]==l2)ans.pb(P(i,a[i]^b[0]));
	}
}
int main(){
	sci(n);
	rep(i,0,n-1)sci(a[i]);
	rep(i,0,n-1)sci(b[i]);
	rep(i,0,n-1){
		s1[i]=a[i]^a[(i+1)%n];
		s1[i+n]=s1[i];
	}
	rep(i,0,n-1)s2[i]=b[i]^b[(i+1)%n];
	extkmp(s1,s2,2*n,n);
	if(!ans.empty() && ans.back().fi>=n)ans.pop_back();//aa a，匹配位置重复算了两次
	for(auto &x:ans){
		printf("%d %d\n",x.fi,x.se);
	}
    return 0;
}