枚举中心去更新答案， 数字过大用log去比较， 斜着的旋转一下坐标， 然后我旋出来好多bug。。。。
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < ) a += mod;}
template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;} int power(int a, int b) {
int ans = ;
while(b) {
if(b & ) ans = 1LL * ans * a % mod;
a = 1LL * a * a % mod; b >>= ;
}
return ans;
} int n, a[N][N], b[N][N];
short row[N][N][], col[N][N][];
short L[N][N], R[N][N], U[N][N], D[N][N];
bool vis[N][N]; LD lg2 = logl(), lg3 = logl(); bool cmp(const PII& a, const PII& b) {
return a.fi * lg2 + a.se * lg3 < b.fi * lg2 + b.se * lg3;
} inline int calcRow(int i, int l, int r, int op) {
return row[i][r][op] - row[i][l][op];
}
inline int calcCol(int j, int l, int r, int op) {
return col[j][r][op] - col[j][l][op];
} PII calc(int a[N][N], int n) {
PII ans = mk(, );
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
if(!a[i][j]) L[i][j] = j, U[i][j] = i;
else L[i][j] = L[i][j - ], U[i][j] = U[i - ][j];
row[i][j][] = row[i][j - ][] + (a[i][j] == );
row[i][j][] = row[i][j - ][] + (a[i][j] == );
col[j][i][] = col[j][i - ][] + (a[i][j] == );
col[j][i][] = col[j][i - ][] + (a[i][j] == );
}
}
for(int i = n; i >= ; i--) {
for(int j = n; j >= ; j--) {
if(!a[i][j]) R[i][j] = j, D[i][j] = i;
else {
if(j == n) R[i][j] = j + ;
else R[i][j] = R[i][j + ];
if(i == n) D[i][j] = i + ;
else D[i][j] = D[i + ][j];
}
}
}
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
if(!a[i][j] || !vis[i][j]) continue;
int d = min({i - U[i][j], D[i][j] - i, j - L[i][j], R[i][j] - j});
PII tmp = mk(, );
tmp.fi += calcRow(i, j - d, j + d - , );
tmp.fi += calcCol(j, i - d, i + d - , );
tmp.se += calcRow(i, j - d, j + d - , );
tmp.se += calcCol(j, i - d, i + d - , );
if(a[i][j] == ) tmp.fi--;
else if(a[i][j] == ) tmp.se--;
if(cmp(ans, tmp)) {
ans = tmp;
}
}
}
return ans;
} int main() {
int mask = ;
scanf("%d", &n);
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
scanf("%1d", &a[i][j]), vis[i][j] = true, mask |= a[i][j];
if(!mask) return puts(""), ;
PII ret1 = calc(a, n);
for(int i = ; i <= * n; i++)
for(int j = ; j <= * n; j++)
b[i][j] = , vis[i][j] = false;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
b[i - j + n][i + j + n] = a[i][j], vis[i - j + n][i + j + n] = true;
int lx = - + n, ly = + + n;
int rx = n - n + n, ry = n + n + n;
int x = (lx + rx) / , y = (ly + ry) / ;
int d = abs(x - lx) + abs(y - ry);
for(int i = ; i <= * n; i++)
for(int j = ; j <= * n; j++)
if(abs(i - x) + abs(j - y) > d)
b[i][j] = ;
PII ret2 = calc(b, * n);
if(cmp(ret1, ret2)) {
printf("%d\n", 1LL * power(, ret2.fi) * power(, ret2.se) % mod);
} else {
printf("%d\n", 1LL * power(, ret1.fi) * power(, ret1.se) % mod);
}
return ;
} /*
*/