题目给了四个轮子，每个轮子上有按顺序排列的n个数，要求适当旋转每个轮子，使得四个轮子相同行数相加和相同。
首先，可以计算出每一行的和应该是多少，记为Sum。然后固定第一个轮子，二重循环枚举2、3轮子，然后O(n)判断1+2+3是否等于Sum-4，这样时间复杂度是O(n^3)。
那么，只要把判断过程复杂度尽量降低就行了。
假设每个轮子最大的数是W，那么我们可以把每个轮子看成一个W+1进制数，然后我们把这个数Hash出来，我们轮子每Shift一位，就相当于Hash把最高位减掉并在最低位加上它。然后，计算Hash(1)+HASH(2)+Hash(3)是否等于Hash(Sum...Sum)， 其中Sum...Sum代表n个Sum的W+1进制数。这样做到了O(1)的判断。但是Hash可能会有重复，那么，我们用一个multimap来保存每一个Hash值对应的若干个可能的4轮子的位置，然后暴力判断这种状态是否真的可行就行了。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <map> 7 #define maxn 2200 8 #define w 4000001 9 #define p 1000000007 10 11 using namespace std; 12 multimap<long long,int> v; 13 multimap<long long,int>::iterator it; 14 15 int a[5][maxn]; 16 long long hash[5]; 17 long long sum,mx,ss; 18 int n; 19 20 bool judge(int i,int j,int k) 21 { 22 for (int o=0;o<n;o++) 23 if (a[1][o]+a[2][(i+o)%n]+a[3][(j+o)%n]+a[4][(k+o)%n]!=sum) return 0; 24 return 1; 25 } 26 27 bool solve() 28 { 29 for (int i=0;i<n;i++) 30 { 31 for (int j=0;j<n;j++) 32 { 33 long long h=(hash[1]+hash[2]+hash[3])%p; 34 for (it=v.lower_bound(h);it!=v.upper_bound(h);it++) 35 { 36 int k=it->second; 37 if (judge(i,j,k)) return 1; 38 } 39 hash[3]=(hash[3]*w%p+a[3][j]*(1-mx+p)%p)%p; 40 } 41 hash[2]=(hash[2]*w%p+a[2][i]*(1-mx+p)%p)%p; 42 } 43 return 0; 44 } 45 46 int main() 47 { 48 int Case; 49 scanf("%d",&Case); 50 for (int t=1;t<=Case;t++) 51 { 52 sum=0; 53 scanf("%d",&n); 54 memset(hash,0,sizeof(hash)); 55 for (int i=1;i<=4;i++) 56 for (int j=0;j<n;j++) 57 { 58 scanf("%d",&a[i][j]); 59 hash[i]=(hash[i]*w%p+a[i][j])%p; 60 sum+=a[i][j]; 61 } 62 sum=sum/n; 63 mx=1,ss=0; 64 for (int i=0;i<n;i++) mx=(mx*w)%p,ss=(ss*w%p+sum)%p; 65 v.clear(); 66 for (int i=0;i<n;i++) 67 { 68 v.insert(make_pair((ss-hash[4]+p)%p,i)); 69 hash[4]=(hash[4]*w%p+a[4][i]*(1-mx+p)%p)%p; 70 } 71 if (solve()) printf("Case %d: Yes ",t); 72 else printf("Case %d: No ",t); 73 } 74 return 0; 75 }