代码求调
查看原帖
代码求调
620253
MvemiY楼主2024/7/27 21:21

马蜂良好,思路是 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;
}
2024/7/27 21:21
加载中...