Solution
首先考虑暴力：
-
枚举同种颜色的格子，假设两点为 \((i,j),(x,y)\)，那么从 \((i,j)\) 到 \((x,y)\) 的方案数即为 \(C_{x-i+y-j}^{x-i}\)。考虑当前颜色有 \(B\) 个，枚举的时间复杂度为 \(O(B^2)\)。
-
考虑枚举每一种颜色，算出这种颜色到其他格子方案数，有递推方程：\(f_{i,j}=f_{i-1,j}+f_{i,j-1}\)，当 \(a_{i,j}\) 为当前颜色时，\(f_{i,j}=1\)。枚举时间复杂度为 \(O(n^2)\)。
再考虑根号分治，把两个暴力拼在一起，当 \(B \leq n\) 时执行第一种暴力，时间复杂度最坏为 \(O(nB^2)\)；当 \(B>n\) 时执行第二种暴力，时间复杂度最坏为 \(O(\frac{n^4}{B})\)，当 \(B=n\) 时，总时间复杂度为 \(O(n^3)\)。
注意在处理逆元的时候应处理到 \(2n\)，因为需要计算 \(inv_{x-i+y-j}\)，而 \(x-i+y-j\) 最大为 \(2n-2\)。
#include<bits/stdc++.h>
#define ll long long
#define x first
#define y second
#define il inline
#define debug() puts("-----")
using namespace std;
typedef pair<int,int> pii;
const int N=410;
const ll Mod=998244353;
int n;
ll f[N][N];
int a[N][N];
vector<pii> v,mp[N*N];
ll inv[N<<1],fac[N<<1];
il ll qmi(ll x,int k){
ll res=1;
while(k){
if(k&1) res=res*x%Mod;
x=x*x%Mod; k>>=1;
} return res;
}
il ll calc(int i,int j,int x,int y){
int P=x-i+y-j,R=x-i;
return fac[P]*inv[P-R]%Mod*inv[R]%Mod;
}
il void init(){
fac[0]=inv[0]=1;
for(int i=1;i<=2*n;i++) fac[i]=fac[i-1]*i%Mod;
inv[2*n]=qmi(fac[2*n],Mod-2);
for(int i=2*n-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%Mod;
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
if(!mp[a[i][j]].size()) v.push_back({i,j});
mp[a[i][j]].push_back({i,j});
}
} init(); ll ans=0;
for(auto u:v){
int col=a[u.x][u.y];
if(mp[col].size()<=n){
for(auto i:mp[col])
for(auto j:mp[col])
if(i.x<=j.x&&i.y<=j.y) ans=(ans+calc(i.x,i.y,j.x,j.y))%Mod;
} else{
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=0;
int col=a[u.x][u.y]; for(auto i:mp[col]) f[i.x][i.y]=1;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1])%Mod,ans=(ans+((a[i][j]==col)?f[i][j]:0))%Mod;
}
} printf("%lld\n",ans); return 0;
}