题解：AT_arc203_c

ARC203C

• $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;
}