本题要求计算在一个 $N\times N$ 的网格中，所有起点和终点标签相同的路径数目。路径只能向右或向下移动。

1. 动态规划方法：定义 $dp [i][j]$ 为从任意起点到 (i,j) 的路径数目。状态转移方程为 $dp [i][j] = dp [i-1][j] + dp [i][j-1]$。当遇到标签为 x 的点时，将 $dp [i][j]$ 累加到答案中。这种方法的时间复杂度为 $O (N²)$。 那么我们针对于每一个x，都要做一遍dp，x的范围是$1\sim N^2$,所以总的时间复杂度是$O(N^4)$。

2. 组合数学方法：对于每对标签相同的点 $(i,j)$ 和 $(x,y)$，如果 $i\leq x$ 且 $j\leq y$，则存在 $C (x-i+y-j, x-i)$ 条路径。这种方法的时间复杂度为 $O (k^2)$，其中 $k$ 是标签出现的次数。最坏情况下，网格中的数字都一样，那么就有$N\times N$个数字，那么我们的总的时间复杂度将会达到$O(N^4)$。

   我们发现，单纯使用上面的一种方法来处理，总的时间复杂度都太大，会导致超时。

   对于上面两种方法，我们知道，动态规划方法的时间复杂度是固定的$O(N^2)$,而组合数学方法的复杂度与数字数量有关，复杂度为$O (k^2)$，所以当一个数字出现次数大于$N$时,我们可以采用动态规划方法，这样时间复杂度会更低。

   时间复杂度的讨论：

   ​ 1.dp把单次复杂度限制在严格的$O(N^2)$,每种数字数量超过$N$,就没有意义。

   ​ 2.所以最坏情况下，是每一种数字的数量都趋近于$N$,总共有$N\times N$ 个数字，因此只有大约$N$种数字会出现,所以总的时间复杂度可以降低至$O(N^3)$。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5e2+10,mod=998244353;

// n为网格大小，a存储网格每个位置的标签
// fac和inv分别存储阶乘和阶乘的逆元
// ans存储最终答案，dp用于动态规划计算路径数
int n,a[N][N],fac[2*N],inv[2*N],ans,dp[N][N];
// val数组存储每个标签对应的所有坐标位置
vector<pair<int,int>> val[N*N];

// 快速幂计算a^b
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

// 计算组合数C(n,m)
int C(int n,int m)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

// 初始化阶乘和阶乘逆元数组
void init()
{
    fac[0]=1;
    for(int i=1;i<=2*n;i++)
        fac[i]=fac[i-1]*i%mod;
    
    inv[2*n]=qpow(fac[2*n],mod-2);
    for(int i=2*n-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
}

// 方法一：直接枚举同一标签的所有点对，计算路径数
void cal(int x)
{
    // 遍历同一标签的所有点对
    for(int i=0;i<val[x].size();i++)
    {
        for(int j=0;j<val[x].size();j++)
        {
            // 如果i点的行或列大于j点，则无法从i走到j，跳过
            if(val[x][i].first>val[x][j].first || val[x][i].second>val[x][j].second) continue;
            
            // 计算x方向和y方向的步数
            int dx=val[x][j].first-val[x][i].first;
            int dy=val[x][j].second-val[x][i].second;
            // 从i到j的路径数为组合数C(dx+dy,dx)
            ans+=C(dx+dy,dx);
            ans%=mod;
        }
    }
}

// 方法二：动态规划计算以每个点为终点的路径数
void DP(int x)
{
    // 初始化dp数组
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            // 当前点的路径数等于上方和左方的路径数之和
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
            
            // 如果当前点的标签等于x
            if(a[i][j]==x)
            {
                // 增加从起点到当前点的路径数（即自身）
                dp[i][j]++;
                dp[i][j]%=mod;
                // 累加到总答案中
                ans+=dp[i][j];
                ans%=mod;
            }
        }
    }
}

void solve()
{
    cin>>n;
    // 读入网格并存储每个标签对应的坐标
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            val[a[i][j]].push_back({i,j});
        }
    }
    // 初始化阶乘和逆元数组
    init();
    
    // 遍历每个标签，根据标签出现次数选择计算方法
    for(int i=1;i<=n*n;i++)
    {
        // 当标签出现次数少于n时，使用组合数直接计算
        if(val[i].size()<n) cal(i);
        // 否则使用动态规划计算
        else DP(i);
    }
    cout<<ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t=1;
    while(t--) solve();
    return 0;
}