[ABC259Ex] Yet Another Path Counting 做题记录

还是不够熟练。

题意简述

一个 $n\times n$ 的网格图，每个格子上有颜色，求满足起点和终点颜色均相同且只向下和向右走的路径条数。可以走 $0$ 步。$n\le 400$。

解法

• 设起点为 $(x,y)$ 终点为 $(z,w)$，则从 $(x,y)$ 到 $(z,w)$ 仅向下和向右走的路径条数为 $\dbinom{x-z+y-w}{x-z}$，可以理解为从起点到终点总共要走 $(x-z+y-w)$ 步，而其中有 $(x-z)$ 步是向下走的，这 $(x-z)$ 步可以在任意时刻走，所以相当于在 $(x-z+y-w)$ 步中选出 $(x-z)$ 步的方案数。
• 颜色之间是独立的，可以分开考虑。
• 对于每种颜色，枚举起点和终点，容易根据上式计算答案，时间复杂度 $O(n^4)$。
• 不过我们忽略了一种最朴素的解题思路。记 $f_{i,j}$ 为以 $(i,j)$ 结尾的合法路径条数，转移为 $f_{i,j}=f_{i,j}+f_{i,j-1}+f_{i-1,j}$。对于所有颜色为当前枚举的颜色的位置 $(i,j)$，初值为 $1$，否则为 $0$。对于每个颜色都要做一遍，时间复杂度 $O(n^4)$。
• 对于这种分颜色处理的问题，很经典的解决方式是对颜色出现次数进行根号分治。记阈值为 $B$，则最多有 $\dfrac {n^2}{B}$ 种颜色出现次数超过 $B$ 次，对这部分做 DP，而对出现次数小于 $B$ 次使用组合数计算。时间复杂度 $O(nB^2+\dfrac{n^4}{B})$，当 $B=n$ 时取到最优，为 $O(n^3)$。

Code

constexpr int N=405;using ll=long long;constexpr ll mod=998244353;
inline ll qpow(ll a,ll b)
{
    ll ret=1;a%=mod;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
int a[N][N];ll f[N][N];
struct dat{int x,y;};
vector<dat>id[N*N];
ll fac[N<<1],ifac[N<<1];
inline ll abs(ll x){return x<0?-x:x;}
inline ll binom(ll n,ll m){return (m<0||n<m)?0:fac[n]*ifac[n-m]%mod*ifac[m]%mod;}
inline ll calc(ll x,ll y,ll z,ll w){return binom(z-x+w-y,z-x);}
inline void init(const int n)
{
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n;cin>>n;init(n*2);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j],id[a[i][j]].emplace_back((dat){i,j});
    ll ans=0;
    for(int i=1;i<=n*n;i++)
    {
        if(!id[i].size()) continue;
        int sz=int(id[i].size());
        if(sz<=n) for(int j=0;j<sz;j++) for(int k=0;k<sz;k++) ans=(ans+calc(id[i][j].x,id[i][j].y,id[i][k].x,id[i][k].y))%mod;
        else
        {
            memset(f,0,sizeof(f));
            for(const dat&j:id[i]) f[j.x][j.y]=1;
            for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) f[j][k]=(f[j][k]+f[j-1][k]+f[j][k-1])%mod;
            for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) if(a[j][k]==i) ans=(ans+f[j][k])%mod;
        }
    }
    cout<<ans<<endl;
}