https://codeforces.com/gym/100500/
题意:
给四个序列,其中$|arr_i|<=1000$
你可以把每个序列循环移动任意次,
最后要求四个序列对应位置累加后得到的最终序列为一个全等序列
题解:
$n^3$暴力显然超时,考虑优化
我们考虑题目的特殊性质,
显然,最终的序列我们可以直接通过总和得到
记为$ans$序列
那么,我们考虑另外一个方向的暴力
固定$arr_1$,枚举$arr_2$的循环同构$loop_k(arr2)$,相加得到$n$个不同的序列$A_i$
固定$arr_3$,枚举$arr_4$的循环同构$loop_k(arr4)$,相加得到$n$个不同的序列$B_i$
再固定每一个$A_i$,枚举$B_j$的每一个$loop_k(B_j)$
看这$2n$个序列两两配对能否凑出最终序列
此时复杂度达到了$n^4$
即,枚举$i,j,k$最后线性判断
我们考虑优化
假设答案的为$i,j,k$且序列长度为$n$
即,$A_i$与$loop_k(B_j)$相加,可以得到$ans$
换句话说,如果我们把$ans$和$loop_k(B_j)$相减,可以得到$A_i$的某一个循环同构
此时,我们就可以同时得到2个优化
1.使用多项式哈希,把所有$A_i$放入哈希表中,
直接枚举$j$即可,此时复杂度为$n^3*hashmap$
2.由于$ans$和$loop_k(B_j)$相减,可以得到$A_i$
又因为$ans$的每一个循环同构都相等,因此我们换一下枚举的顺序
即$ans$和$B_j$相减,可以得到$loop_x(A_i)$,$x$为未知数
此时利用$Rabbin-Karp$的思想,枚举他的循环同构哈希值,就可以$n^2*hashmap$的解决问题了
在这里也提供另外一个方法:
如果我们把每一个$A_i$都变成它的最小表示$minrep(A_i)$,再放入哈希表
同时,把$ans$和$B_j$相减得到的$loop_x(A_i)$也变为它的最小表示$minrep(loop_x(A_i))$
由于$minrep(A_i)$恒等于$minrep(loop_x(A_i))$
然后我们也可以直接通过哈希值快速判断了
复杂度也为$n^2*hashmap$
#include<bits/stdc++.h>
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
using namespace std;//head
const int maxn=1e3+10,maxm=2e6+10;
int casn,n,m,k;
int a[5][maxn];
int minrep(int *s,int n){
int i=0,j=1,k=0,t;
while(i<n&&j<n&&k<n){
t=s[i+k>=n?i+k-n:i+k]-s[j+k>=n?j+k-n:j+k];
if(!t) ++k;
else {
if(t>0) i+=k+1;
else j+=k+1;
if(i==j) ++j;
k=0;
}
}
return min(i,j);
}
int id[maxn*2+10];
const ull base=1e9+7;
int b[maxn];
ull gethash(int *s,int n){
int pos=minrep(s,n);
ull res=0;
rep(i,0,n-1) res=res*base+s[id[pos+i]];
return res;
}
unordered_set<ull> vis;
ull ans;
bool check(int i){
rep(j,0,n-1)b[j]=ans-a[3][j]-a[4][id[j+i]];
return vis.count(gethash(b,n));
}
int main() {IO;
cin>>casn;
int kase=0;
while(casn--){
cin>>n;
ull sum=0;
rep(i,1,4){
rep(j,0,n-1){
cin>>a[i][j];
sum+=a[i][j];
}
}
if(sum%n){
cout<<"Case "<<++kase<<": No
";
continue;
}
vis.clear();
ans=sum/n;
rep(i,0,2*n) id[i]=i%n;
rep(i,0,n-1){
rep(j,0,n-1) b[j]=a[1][j]+a[2][id[i+j]];
vis.insert(gethash(b,n));
}
bool flag=0;
rep(i,0,n-1){
if(check(i)) {
flag=1;
break;
}
}
if(flag)cout<<"Case "<<++kase<<": Yes
";
else cout<<"Case "<<++kase<<": No
";
}
}