马蜂良好,思路是 hash 维护前缀和、前缀平方和、以及给位置设置权值。
调出来 v 你 10 块。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55, mod = 998244353;
typedef long long ll;
inline ll read(){
ll x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
ll n, a[MAXN][MAXN], b[MAXN][MAXN], pre1[MAXN][MAXN], pre2[MAXN][MAXN], pre3[MAXN][MAXN], pre4[MAXN][MAXN], pre5[MAXN][MAXN], pre6[MAXN][MAXN], az[MAXN], mi[MAXN], c[MAXN][MAXN], d[MAXN][MAXN], e[MAXN][MAXN], f[MAXN][MAXN], pre7[MAXN][MAXN], pre8[MAXN][MAXN];
ll QuickPow(ll x, ll k){
ll res = 1;
while(k){
if(k & 1){
res *= x;
res %= mod;
}
x *= x;
x %= mod;
k >>= 1;
}
return res;
}
void init(){
az[0] = mi[0] = 1;
az[1] = QuickPow(2, mod-2);
mi[1] = 2;
for(int i = 2; i <= 50; i++)
az[i] = az[i-1] * az[1] % mod, mi[i] = mi[i-1]*2%mod;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
pre1[i][j] = pre1[i-1][j] + pre1[i][j-1] - pre1[i-1][j-1] + a[i][j]; pre1[i][j] %= mod;
pre2[i][j] = pre2[i-1][j] + pre2[i][j-1] - pre2[i-1][j-1] + b[i][j]; pre2[i][j] %= mod;
pre3[i][j] = pre3[i-1][j] + pre3[i][j-1] - pre3[i-1][j-1] + a[i][j]%mod*a[i][j]%mod; pre3[i][j] %= mod;
pre4[i][j] = pre4[i-1][j] + pre4[i][j-1] - pre4[i-1][j-1] + b[i][j]%mod*b[i][j]%mod; pre4[i][j] %= mod;
c[i][j] = c[i][j-1] + a[i][j] * mi[j], c[i][j] %= mod;
pre5[i][j] = pre5[i-1][j] + pre5[i][j-1] - pre5[i-1][j-1] + c[i][j]; pre5[i][j] %= mod;
d[i][j] = d[i][j-1] + b[i][j] * mi[j], d[i][j] %= mod;
pre6[i][j] = pre6[i-1][j] + pre6[i][j-1] - pre6[i-1][j-1] + d[i][j]; pre6[i][j] %= mod;
e[i][j] = e[i-1][j] + a[i][j] * mi[i], e[i][j] %= mod;
pre7[i][j] = pre7[i-1][j] + pre7[i][j-1] - pre7[i-1][j-1] + e[i][j]; pre7[i][j] %= mod;
f[i][j] = f[i-1][j] + b[i][j] * mi[i], f[i][j] %= mod;
pre8[i][j] = pre8[i-1][j] + pre8[i][j-1] - pre8[i-1][j-1] + f[i][j]; pre8[i][j] %= mod;
}
}
}
bool work(int xa, int ya, int xb, int yb, int len){
int xa2 = xa+len-1, ya2 = ya+len-1;
int xb2 = xb+len-1, yb2 = yb+len-1;
ll suma, sumb;
suma = pre1[xa2][ya2] - pre1[xa2][ya-1] - pre1[xa-1][ya2] + pre1[xa-1][ya-1]; suma = (suma % mod + mod) % mod;
sumb = pre2[xb2][yb2] - pre2[xb2][yb-1] - pre2[xb-1][yb2] + pre2[xb-1][yb-1]; sumb = (sumb % mod + mod) % mod;
if(suma != sumb) return false;
suma = pre3[xa2][ya2] - pre3[xa2][ya-1] - pre3[xa-1][ya2] + pre3[xa-1][ya-1]; suma = (suma % mod + mod) % mod;
sumb = pre4[xb2][yb2] - pre4[xb2][yb-1] - pre4[xb-1][yb2] + pre4[xb-1][yb-1]; sumb = (sumb % mod + mod) % mod;
if(suma != sumb) return false;
suma = pre5[xa2][ya2] - pre5[xa2][ya-1] - pre5[xa-1][ya2] + pre5[xa-1][ya-1]; suma = (suma % mod + mod) % mod;
sumb = pre6[xb2][yb2] - pre6[xb2][yb-1] - pre6[xb-1][yb2] + pre6[xb-1][yb-1]; sumb = (sumb % mod + mod) % mod;
suma *= az[ya-1], suma %= mod;
sumb *= az[yb-1], sumb %= mod;
if(suma != sumb) return false;
suma = pre7[xa2][ya2] - pre7[xa2][ya-1] - pre7[xa-1][ya2] + pre7[xa-1][ya-1]; suma = (suma % mod + mod) % mod;
sumb = pre8[xb2][yb2] - pre8[xb2][yb-1] - pre8[xb-1][yb2] + pre8[xb-1][yb-1]; sumb = (sumb % mod + mod) % mod;
suma *= az[xa-1], suma %= mod;
sumb *= az[xb-1], sumb %= mod;
if(suma != sumb) return false;
return true;
}
int main(){
n = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
a[i][j] = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
b[i][j] = read();
init();
int ans = 0;
for(int xa = 1; xa <= n; xa++){
for(int ya = 1; ya <= n; ya++){
for(int xb = 1; xb <= n; xb++){
for(int yb = 1; yb <= n; yb++){
if(min(min(n-xa+1,n-ya+1),min(n-xb+1,n-yb+1)) < ans) break;
for(int len = min(min(n-xa+1,n-ya+1),min(n-xb+1,n-yb+1)); len >= 1; len--){
if(work(xa, ya, xb, yb, len)){
ans = max(ans, len);
break;
}
}
}
}
}
}
cout << ans;
return 0;
}