2025 ICPC武汉邀请赛 G [根号分治 容斥原理+DP]

Problem - G - Codeforces观察题目我们可以用贡献法 计算每个格子的贡献然后累加起来对于重复的部分我们要减去1.路径数量首先计算两个位置间有多少种路径互通我们可以利用组合数进行计算当两点之间的横坐标距离差的绝对值为x,纵坐标的距离差值为y那么有方案数ansc(xy,x)或c(xy,y) 二者本身等价实际意义可以理解为进行xy次移动操作其中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_jx_iy_jy_i也就是能转移到(i,j)的所有同种方格;从起点到该点 且 第一次经过的P元素为该点的 方案数从起点到(i,j)点的方案数 -c(x_i-x_jy_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(nm-i-j,n-i) ) 其中所有的格子(i,j)都为p元素 实际意义也就是从起点到(i,j) 且 不经过相同P元素的方案数 * 从i,j到终点的方案数时间复杂度为o(nm);总和考虑两种方案 当相同元素数量k sqrt( n * m ) 那么方案1的时间复杂度就会高于o(n*m) 此时我们选择方案2同理当ksqrt( n * m )的时候我们选择方案1 时间复杂度小于o(n*m)代码实现#include bits/stdc.h using namespace std; #define int long long const int mod998244353; const int N1e55,MOD998244353; long long fac[N],inv[N]; long long qpow(long long a,long long b,long long mod){ long long ans1; for(;b;b1){ if(b1){ ans(1LL*ans*a)%mod; } a(1LL*a*a)%mod; } return ans; } void init(int n){ fac[0]inv[0]1; for(int i1;in;i)fac[i](fac[i-1]*i)%MOD; inv[n]qpow(fac[n],MOD-2,MOD); for(int in-1;i1;i--)inv[i]inv[i1]*(i1)%MOD; } long long c(int n,int m){ if(nm)return 0; return fac[n]*inv[m]%MOD*inv[n-m]%MOD; } void solve(){ int n,m; cinnm; vectorvectorinta(n2,vectorint(m2,0)); unordered_mapint,vectorpairint,intmp; vectorintcnt(n*m2,0); int sqsqrt(n*m); for(int i1;in;i){ for(int j1;jm;j){ cina[i][j]; cnt[a[i][j]]; if(cnt[a[i][j]]sq)mp[a[i][j]].push_back({i,j}); } } int ans0; vectorboolvis(n*m1,0); for(int ii1;iin;ii){ for(int jj1;jjm;jj){ if(vis[a[ii][jj]])continue; vis[a[ii][jj]]1; if(cnt[a[ii][jj]]sq){ auto vmp[a[ii][jj]]; sort(v.begin(),v.end()); int szv.size(); vectorintdp(sz1); for(int i0;isz;i){ dp[i]c(v[i].firstv[i].second-2,v[i].first-1); for(int j0;ji;j){ if(v[j].firstv[i].firstv[j].secondv[i].second){ dp[i](dp[i]-dp[j]*c(v[i].first-v[j].firstv[i].second-v[j].second,v[i].first-v[j].first)%modmod)%mod; } } } int res0; for(int i0;isz;i){ res(resdp[i]*c(nm-v[i].first-v[i].second,n-v[i].first)%mod)%mod; } ans(ansres)%mod; }else { vectorvectorintdp(n1,vectorint(m1,0)); dp[1][0]1; int res0; for(int i1;in;i){ for(int j1;jm;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(resdp[i][j]*c(nm-i-j,n-i)%mod)%mod; } } } ans(ansres)%mod; } } } coutans\n; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(N-3); int t; cint; while(t--)solve(); return 0; }