题解：AT_arc203_c [ARC203C] Destruction of Walls
Eddie08012025 · · 题解
分析
首先发现
总墙数
-
-
-
-
- 路径长度为 $h+w-2$。此时可能会重复算一种情况，就是开放了一个二乘二方格中的所有墙，此时有两种走法，因此会将答案多算 $1$，考虑如何处理。 假设这个二乘二方格的左上端点为 $(i,j)$，多算的方案数即为从 $(1,1)\rarr(i,j)$ 的方案数乘 $(i+1,j+1)\rarr(h,w)$ 的方案数。总多算方案数为 $\sum_{i=1}^{h-1}\sum_{j=1}^{w-1} \binom{i+j-2}{i-1}\binom{h+w-i-j-2}{h-i-1}$。 那么这里我给出代数推导：（其中第一步先化简内层，将 $i$ 当作常量，发现上指标相加不变，使用上指标卷积 $\sum_{i=0}^{h}\binom{i}{a}\binom{h-i}{b} = \binom{h+1}{a+b+1}$ 可以先消掉一维。） $\sum_{i=1}^{h-1}\sum_{j=1}^{m-1} \binom{i+j-2}{i-1}\binom{h+w-i-j-2}{h-i-1}=\sum_{i=1}^{h-1}\binom{i+j-2}{i-1}\binom{h+w-3}{h-1}=\binom{h+w-3}{h-1}\times(h-1) - 路径长度为
h+w ，此时没有多余的步数，这种情况出现在向上走了一步后面再向下走了一步或向左走了一步后面再向右走了一步，若向上走了一步，那么在竖直方向上的总步数是h+1 ，而在水平方向上的总步数依然是w−1 。发现，如果有一步是向上的，那么它的上一步和下一步都必须是向右的，那么我们将右上右绑定在一起当作向下走，最后乘以在向下走的步数中选取一步右上右的方案数（这一步不能出现在第一步或最后一步），有方案数\binom{h+w-2}{h+1}\times(h-1) 。向左走一步同理。
这种方案的方案数为：
\binom{h+w-2}{h-1}\binom{p-f}{2}-\binom{h+w-3}{h-1}\times(h-1)+\binom{h+w-2}{h+1}\times(h-1)+\binom{h+w-2}{w+1}\times(w-1) - 路径长度为
代码
#include<bits/stdc++.h>
using namespace std;
int t,n,m,k,jie[400005],inv[400005];
const int mod=998244353;
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1)ans=1ll*ans*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return ans;
}
long long C(int x,int y){
if(x==0||y==0)return 1;
if(x==y)return 1;
return 1ll*jie[x]*inv[x-y]%mod*inv[y]%mod;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
jie[0]=1;
for(int i=1;i<=400000;i++){
jie[i]=1ll*jie[i-1]*i%mod;
inv[i]=qpow(jie[i],mod-2);
}
while(t--){
cin>>n>>m>>k;
int len=n+m-2;
int ge=(1ll*(n-1)*m+1ll*(m-1)*n)%mod;
if(k<len){
cout<<"0\n";
continue;
}if(k==len){
cout<<C(len,n-1)<<'\n';
continue;
}if(k==len+1){
cout<<1ll*C(len,n-1)*(ge-len+mod)%mod<<"\n";
continue;
}
cout<<(1ll*C(len,n-1)*(ge-len+mod)%mod*(ge-len-1+mod)%mod*inv[2]%mod-1ll*C(n+m-3,n-1)*(n-1)%mod+1ll*C(n+m-2,n+1)*(n-1)%mod+1ll*C(n+m-2,m+1)*(m-1)%mod+(long long)mod)%mod<<"\n";
}
return 0;
}