题解：AT_arc203_c

AC_Lover · 2025-08-04 16:56:55 · 题解

ARC203C

注意到加粗的 K\le H+W，分讨一下：

• K<H+W-2

  此时无法形成一条可行的路径，答案为 0。

• K=H+W-2

  相当于往右下走的格路计数，方案数就是 \binom{H+W-2}{H-1}。

• K=H+W-1

  相当于格路上随便加一条多余的边，记多余位置 t=H(W-1)+W(H-1)-(H+W-2)，方案数：

  \binom{H+W-2}{H-1}\times t
• K=H+W

  不难发现此时最短路径长度有 H+W-2 和 H+W 两种，分讨：

  • 长度为 H+W-2

  先考虑随便加两条边，方案数是：

  \binom{H+W-2}{H-1}\times \binom{t}{2}

  但是这样会算重，考虑一个折角，即

  (i,j)\to (i,j+1)\to (i+1,j+1) (i,j)\to (i+1,j)\to (i+1,j+1)

  同时出现，那么分别考虑两个折角的时候就会算重。于是容斥掉这种折角，我们将两个折角看做从 (i,j)\to (i+1,j+1) 的向右下的移动方式，这其实相当于把原来格路中的一个 \rightarrow 和 \downarrow 替换成了一个 \searrow，剩下 H+W-2-2=H+W-4 个 \rightarrow,\downarrow，排列完再往里面插一个 \searrow，容斥方案数就是

  \binom{H+W-4}{H-2}\times (H+W-3)
  • 长度为 H+W

  我们令 \rightarrow \downarrow 为正方向，那么这种情况相当于在某个地方 \uparrow，然后某处再 \downarrow，或是在某个地方 \leftarrow，然后某处再 \rightarrow，为了方便我们可以只考虑往上走的情况，左同理。

  挖掘这个 \uparrow 放在什么位置才是合法的。发现，这个向上一定是 \rightarrow \uparrow\rightarrow 的情况，并且不能放在第一个 \downarrow 的前面和最后一个 \downarrow 的后面。

  考虑这样组合：放好 \downarrow，放 \rightarrow \uparrow\rightarrow（同时保证其不在开头和结尾），放 \rightarrow。

  总共有 H-1+1=H 个 \downarrow，所以除掉开头结尾有 H-1 个位置，放 \rightarrow \uparrow\rightarrow 就有 H-1 种方案。

  然后再插 W-1-2=W-3 个 \rightarrow，根据多重集的组合数有 \binom{H+1+W-3}{W-3}=\binom{H+W-2}{W-3} 种方案。

  因此对于上，总方案数就是

  (H-1)\times \binom{H+W-2}{W-3}

  对于左同理计算即可。

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int mod=998244353;
inline int Mod(int x) { return x<0 ? x+mod : (x>=mod ? x-mod : x); }
inline void adm(int &x,int y) { x=Mod(x+y); }
inline int qmi(ll a,int b)
{
    ll res=1;
    while (b)
    {
        if (b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

const int N=400000;
int fac[N+10],infac[N+10];
inline int binom(int a,int b) 
{ 
    if (a<0 || b<0 || a<b) return 0;
    return (ll)fac[a]*infac[b]%mod*infac[a-b]%mod; 
}

int main()
{
    fac[0]=1;
    for (int i=1;i<=N;i++) fac[i]=(ll)fac[i-1]*i%mod;
    infac[N]=qmi(fac[N],mod-2);
    for (int i=N-1;i>=0;i--) infac[i]=(ll)infac[i+1]*(i+1)%mod;

    int T;
    cin >> T;
    while (T--)
    {
        int h,w,k;
        cin >> h >> w >> k;
        int t=(2ll*h*w-h-w-(h+w-2))%mod;
        if (k<h+w-2) cout << "0\n";
        else if (k==h+w-2) cout << binom(h+w-2,h-1) << "\n";
        else if (k==h+w-1) cout << 1ll*binom(h+w-2,h-1)*t%mod << "\n";
        else 
        {
            int u=1ll*binom(h+w-2,h-1)*t%mod*Mod(t-1)%mod*infac[2]%mod;
            int s=1ll*binom(h+w-4,h-2)*(h+w-3)%mod;

            int up=1ll*(h-1)*binom(h+w-2,w-3)%mod;
            int lft=1ll*(w-1)*binom(h+w-2,h-3)%mod;

            int ans=((ll)Mod(u-s)+up+lft)%mod;
            cout << ans << "\n";
        }
    }

    return 0;
}