AtCoder ARC #203 : C - Destruction of Walls

細かい場合分けが地味にめんどい。
https://atcoder.jp/contests/arc203/tasks/arc203_c

問題

整数H,W,Kが与えられる。
H*Wのグリッドがあり、セルとセルの間は壁がある。
壁をK枚壊したとき、左上から右下セルに移動できるような破壊の仕方は何通りあるか。

解法

最短経路で(H+W-2)枚壁を壊す必要がある。

• K＜H+W-2の時
  • 到達不可なので0通り
• K=H+W-2の時
  • 最短経路に至る壁だけ壊すので、これは結局最短経路の数と等しくC(H+W-2,H-1)通り
• K=H+W-1の時
  • 最短経路に至る壁+1枚だけ壊す。壁の数は(2HW-H-W)枚あり、最短経路を作るのに(H+W-2)枚壊すので残り1枚の壊し方を考えると、C(H+W-2,H-1)*(2HW-2H-2W-2)通り
• K=H+W-2の時
  • 最短経路で移動する場合
    • 上と同じ考え方とすると、C(H+W-2,H-1)*C(2HW-2H-2W-2,2)通り
    • ただし、2*2の領域について中の壁4枚を壊すと、最短経路の移動方法が2パターンある場合がある。上記掛け算ではこのケースを二重カウントするので、これを除こう。これは、(H-1)*(W-1)のグリッドにおける最短経路のうち、1マスを選んで内部を2*2にすると考えればよく、C(H+W-4,W-2)*(H+W-3)通りである。
  • 最短経路でない場合
    • 途中で「下左下」または「右上右」を挟むと、最短経路ではなく、かつ壊す壁はすべて経路上になる。
    • 前者を考えると、下移動が(H-3)回、「下左下」移動が1回、右移動がW回である。このうち、下左下の移動は最初の右移動の後で、最後の右移動の前である必要がある。これは(H+W-2)!/(H-3)!1!W!*(1-2/(W+1))となる。

int T;
ll H,W,K;
const ll mo=998244353;
const int NUM_=1400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>K;
		int need=H-1+W-1;
		if(K<need) {
			cout<<0<<endl;
		}
		else if(K==need) {
			cout<<comb(need,W-1)<<endl;
		}
		else if(K==need+1) {
			ll sum=1LL*(H-1)*W+H*(W-1);
			cout<<comb(need,W-1)*((sum-need)%mo)%mo<<endl;
		}
		else {
			assert(K==need+2);
			ll sum=(1LL*(H-1)*W+H*(W-1)-need)%mo;
			ll sum2=sum*(sum-1)/2%mo;
			ll ret=comb(need,W-1)*sum2%mo;
			
			//2*2で自由に行ける場所がある
			ll pat2=comb(H-2+W-2,W-2)*(H+W-3)%mo;
			ret=(ret-pat2+mo)%mo;
			
			//下左下移動
			//下左下移動は、右移動の前と後以外で使える
			if(H>=3) {
				x=H-3,y=1,k=W;
				ll a=fact[x+y+k]*factr[x]%mo*factr[k]%mo-fact[x+y+k]*factr[x]%mo*factr[k+y]*2%mo+mo;
				ret+=a;
			}
			//右上右
			if(W>=3) {
				x=W-3,y=1,k=H;
				ll a=fact[x+y+k]*factr[x]%mo*factr[k]%mo-fact[x+y+k]*factr[x]%mo*factr[k+y]*2%mo+mo;
				ret+=a;
			}
			
			cout<<ret%mo<<endl;
		}
	}
}

まとめ

最短経路を通らないケースを網羅するのに手間取った。