题目给了四个*，每个*上有按顺序排列的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*的位置，然后暴力判断这种状态是否真的可行就行了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define maxn 2200
#define w 4000001
#define p 1000000007 using namespace std;
multimap<long long,int> v;
multimap<long long,int>::iterator it; int a[][maxn];
long long hash[];
long long sum,mx,ss;
int n; bool judge(int i,int j,int k)
{
for (int o=;o<n;o++)
if (a[][o]+a[][(i+o)%n]+a[][(j+o)%n]+a[][(k+o)%n]!=sum) return ;
return ;
} bool solve()
{
for (int i=;i<n;i++)
{
for (int j=;j<n;j++)
{
long long h=(hash[]+hash[]+hash[])%p;
for (it=v.lower_bound(h);it!=v.upper_bound(h);it++)
{
int k=it->second;
if (judge(i,j,k)) return ;
}
hash[]=(hash[]*w%p+a[][j]*(-mx+p)%p)%p;
}
hash[]=(hash[]*w%p+a[][i]*(-mx+p)%p)%p;
}
return ;
} int main()
{
int Case;
scanf("%d",&Case);
for (int t=;t<=Case;t++)
{
sum=;
scanf("%d",&n);
memset(hash,,sizeof(hash));
for (int i=;i<=;i++)
for (int j=;j<n;j++)
{
scanf("%d",&a[i][j]);
hash[i]=(hash[i]*w%p+a[i][j])%p;
sum+=a[i][j];
}
sum=sum/n;
mx=,ss=;
for (int i=;i<n;i++) mx=(mx*w)%p,ss=(ss*w%p+sum)%p;
v.clear();
for (int i=;i<n;i++)
{
v.insert(make_pair((ss-hash[]+p)%p,i));
hash[]=(hash[]*w%p+a[][i]*(-mx+p)%p)%p;
}
if (solve()) printf("Case %d: Yes\n",t);
else printf("Case %d: No\n",t);
}
return ;
}