2025 ICPC武汉邀请赛 G [根号分治 容斥原理+DP]
Problem - G - Codeforces
观察题目，我们可以用贡献法， 计算每个格子的贡献，然后累加起来，对于重复的部分我们要减去
1.路径数量
首先，计算两个位置间有多少种路径互通，我们可以利用组合数进行计算：
当两点之间的横坐标距离差的绝对值为x,纵坐标的距离差值为y，那么有方案数ans=c(x+y,x)或c(x+y,y) 二者本身等价
实际意义可以理解为：进行x+y次移动操作，其中x次是横向移动的方案（或者y次是向下移动的方案）
2.计算同种方格的总方案数
对于一种方格，我们记方格中的元素为p;
方案1 ：
对于每个方格 如果他的元素为p ，由于一个元素在某条路径上出现多次时只有一次的贡献， 所以该元素第一次出现的所有位置到终点方案数之和就是答案，那么总的方案数就是
我们要算的是：所有「第一次经过数值 p」在点(i,j)的路径数公式：f(i,j) = 起点到(i,j)总方案数 - Σ( 起点到(u,v)方案数 × (u,v)到(i,j)方案数 )其中(u,v)是所有比(i,j)更靠左上的同值点（u≤i, v≤j且(u,v)≠(i,j)）。
最终点(i,j)对p的贡献 =f(i,j) × (i,j)到终点的方案数。
我们记(x_i,y_i)为该点坐标，(x_j,y_j)为所有同种的方格且（x_j<=x_i&&y_j<=y_i）也就是能转移到(i,j)的所有同种方格;
从起点到该点 且 第一次经过的P元素为该点的 方案数=从起点到(i,j)点的方案数 -c(x_i-x_j+y_i-y_j , x_i -x_j)
该方案数*该点到终点的方案数 = 该点的贡献
时间复杂度为o(k^2)，k为该相同元素的数目
方案2 DP:
对于同种元素p
我们n*m的遍历一遍，进行转移 ，记dp[i][j]为到达（i,j)的方案数 ，其中如果有和(i,j)相同的元素，我们要视作障碍，这样的话dp[i][j]表达的意思就是不经过与 p 相同的元素走到(i,j)的方案数 。类似于过河卒问题的DP;
DP的转移就是：dp[i][j]= dp[i-1][j] * (a[i-1][j]!=p) + dp[i][j-1]*(a[i][j-1]!=p)
对于所有为元素P的格子，总的方案数就是：( dp[i][j]*c(n+m-i-j,n-i) )， 其中所有的格子(i,j)都为p元素 ， 实际意义也就是：从起点到(i,j) 且 不经过相同P元素的方案数 * 从（i,j）到终点的方案数
时间复杂度为o(nm);
总和考虑两种方案 当相同元素数量k >sqrt( n * m ) 那么方案1的时间复杂度就会高于o(n*m) 此时我们选择方案2
同理当k<sqrt( n * m )的时候我们选择方案1 时间复杂度小于o(n*m)；
代码实现：
#include <bits/stdc++.h> using namespace std; #define int long long const int mod=998244353; const int N=1e5+5,MOD=998244353; long long fac[N],inv[N]; long long qpow(long long a,long long b,long long mod){ long long ans=1; for(;b;b>>=1){ if(b&1){ ans=(1LL*ans*a)%mod; } a=(1LL*a*a)%mod; } return ans; } void init(int n){ fac[0]=inv[0]=1; for(int i=1;i<=n;i++)fac[i]=(fac[i-1]*i)%MOD; inv[n]=qpow(fac[n],MOD-2,MOD); for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%MOD; } long long c(int n,int m){ if(n<m)return 0; return fac[n]*inv[m]%MOD*inv[n-m]%MOD; } void solve(){ int n,m; cin>>n>>m; vector<vector<int>>a(n+2,vector<int>(m+2,0)); unordered_map<int,vector<pair<int,int>>>mp; vector<int>cnt(n*m+2,0); int sq=sqrt(n*m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; cnt[a[i][j]]++; if(cnt[a[i][j]]<=sq)mp[a[i][j]].push_back({i,j}); } } int ans=0; vector<bool>vis(n*m+1,0); for(int ii=1;ii<=n;ii++){ for(int jj=1;jj<=m;jj++){ if(vis[a[ii][jj]])continue; vis[a[ii][jj]]=1; if(cnt[a[ii][jj]]<=sq){ auto &v=mp[a[ii][jj]]; sort(v.begin(),v.end()); int sz=v.size(); vector<int>dp(sz+1); for(int i=0;i<sz;i++){ dp[i]=c(v[i].first+v[i].second-2,v[i].first-1); for(int j=0;j<i;j++){ if(v[j].first<=v[i].first&&v[j].second<=v[i].second){ dp[i]=(dp[i]-dp[j]*c(v[i].first-v[j].first+v[i].second-v[j].second,v[i].first-v[j].first)%mod+mod)%mod; } } } int res=0; for(int i=0;i<sz;i++){ res=(res+dp[i]*c(n+m-v[i].first-v[i].second,n-v[i].first)%mod)%mod; } ans=(ans+res)%mod; }else { vector<vector<int>>dp(n+1,vector<int>(m+1,0)); dp[1][0]=1; int res=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=((dp[i-1][j]*(a[i-1][j]!=a[ii][jj]))+(dp[i][j-1]*(a[i][j-1]!=a[ii][jj])))%mod; if(a[i][j]==a[ii][jj]){ res=(res+dp[i][j]*c(n+m-i-j,n-i)%mod)%mod; } } } ans=(ans+res)%mod; } } } cout<<ans<<'\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(N-3); int t; cin>>t; while(t--)solve(); return 0; }