1011-Kidnapper's Matching Problem
题意
给两个长度分别为(n)和(m)的数组(a,b)，和一个集合(S)，(a)中一个长度为(m)的子段和(b)匹配需满足(a_l oplus b_1,a_{l+1}oplus b_2,dots,a_{l+m-1} oplus b_m)都能被集合(S)中的若干个数异或得到。
计算
[sum_{i = 1}^{n - m + 1} [(a_i, a_{i + 1}, cdots, a_{i + m - 1}) ext{ matches } b] cdot 2^{i - 1} mod (10^9 + 7)
]
分析
考虑如何判断 (x oplus y in 2_{oplus}^{S})．先求出 (S) 的线性基 (B)．
断言．假设 (x, y) 消去 (B) 中的位后得到的数分别为 (x ′ , y′) , 那么 (x oplus y in 2_{oplus}^{S}) 的充要条件是 (x ′ = y ′)．
充分性: (x oplus y) 必然能写成 (x ′ oplus y ′) 再异或上 (B) 中的一些数的形式．在 (x ′ = y ′) 时即 (x oplus y in 2_{oplus}^{S})．
必要性: 考虑反证．因为 (x ′ , y′) 都不包含 (B) 中的位, 所以 (x ′ oplus y ′) 不包含 (B) 中的位．又因为 (x ′ e y ′) , 所以 (x ′ oplus y ′) 非零, 那么 (x ′ oplus y ′) 一定包含 (B) 无法表示的位, 所以 (x oplus y otin 2_{oplus}^{S})． 接下来问题就变简单了．我们只需要把序列 (a, b) 都消去 (B) 中的位, 然后做 (KMP) 即可．时间复杂度 (O((N + M + K)log V ))．
Code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=2e5+10;
const int inf=1e9;
int T,n,m,k;
int a[N],b[N],nex[N];
int p[40];
ll f[N];
void ins(int x){
per(i,29,0) if(x>>i&1){
if(!p[i]){
p[i]=x;
break;
}
x^=p[i];
}
}
int gao(int x){
per(i,29,0) if(x>>i&1){
x^=p[i];
}
return x;
}
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
f[0]=1;
rep(i,1,200000) f[i]=f[i-1]*2%mod;
scanf("%d",&T);
while(T--){
memset(p,0,sizeof(p));
scanf("%d%d%d",&n,&m,&k);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,m) scanf("%d",&b[i]);
rep(i,1,k){
int x;
scanf("%d",&x);
ins(x);
}
rep(i,1,n) a[i]=gao(a[i]);
rep(i,1,m) b[i]=gao(b[i]);
for(int i=2,j=0;i<=m;i++){
while(j&&b[j+1]!=b[i]) j=nex[j];
if(b[j+1]==b[i]) ++j;
nex[i]=j;
}
ll ans=0;
for(int i=1,j=0;i<=n;i++){
while(j&&b[j+1]!=a[i]) j=nex[j];
if(b[j+1]==a[i]) ++j;
if(j==m){
ans=(ans+f[i-m])%mod;
j=nex[j];
}
}
printf("%lld
",ans);
}
return 0;
}