Description

有一个N×M的矩阵，每个位置有两个值a,b，代表一个同余方程x≡a(modb)

一个子矩阵是合法的，当且仅当将其中的每个同余方程联立时有解
求合法子矩阵最大面积
N,M≤150,0≤a<b<40

Solution

考虑如何判断两个同余方程是否有公共解
方程化为x=a1+k1b1=a2+k2b2
a1−a2=k1b1−k2b2
根据扩展欧几里得判断有解的方法，方程有解当且仅当gcd(b1,b2)|a1−a2
预处理gcd，我们就可以O(1)判断了

考虑枚举下边界，枚举右边界
左边界从右向左扩展，上边界不断下移

现在考虑如何计算新扩展出来的一列与原本的矩阵是否匹配

我们要判断黄色的部分和绿色+棕色的这个矩形是否合法
然而我们之前已经做过R-1和i-1了
也就是说上面的长的矩形（L~R,下边界为i-1）是否合法和左边高的巨鼎(L~R-1，下边界为i)这两个矩形我们都已经知道它是否合法

那么只需要判断棕色的一个和黄色匹配是否合法即可
可以用一个三维数组表示卡住上，下，右边界最左可以延伸到哪里
这样就O(N4)解决本题（并且实际上还要除一个常数）

Code

include

include

include

include

include

include

define fo(i,a,b) for(int i=a;i<=b;i++)

define fod(i,a,b) for(int i=a;i>=b;i–)

define N 152

using namespace std;
int a[N][N],b[N][N],gd[41][41],ct[N][N][N],n,m;
int gcd(int x,int y)
{
return(y)?gcd(y,x%y):x;
}
bool pd(int i,int j,int x,int y)
{
return((a[i][j]-a[x][y])%gd[b[i][j]][b[x][y]]==0);
}
int main()
{
cin>>n>>m;
fo(i,1,n)
fo(j,1,m) scanf(“%d”,&a[i][j]);
fo(i,1,n)
fo(j,1,m) scanf(“%d”,&b[i][j]);
fo(i,1,40) fo(j,1,40) gd[i][j]=gcd(i,j);
int ans=0;
fo(i,1,n)
{
fo(r,1,m)
{
int hi=i;
bool bz=1;
fod(p,i,1)
{
bz=1;
fod(q,i,p+1) if(!pd(p,r,q,r)){bz=0;break;}
if(!bz) {hi=p+1;break;}
else ct[i][r][p]=1;
}
if(bz) hi=1;
ans=max(ans,i-hi+1);
fod(l,r-1,1)
{
while(hi<=i&&(ct[i][l][hi]==0||(i!=hi&&ct[i-1][r][hi]