AtCoder ARC #114 : E - Paper Cutting 2

これ解けなかったの良くないなぁ。
https://atcoder.jp/contests/arc114/tasks/arc114_e

問題

N*Mのグリッド上の紙があり、うち異なる2マスが指定されている。
グリッドの線に沿って、縦か横のラインを選び、紙を2つに切断する。各ラインを選ぶ確率は等確率とする。
もし指定2マスが切断により分かれたらそれで終了、別れなければまた切断を行う。

最後、指定2マスが分かれるまでの切断回数の期待値を求めよ。

解法

指定2マスを囲う最小の矩形を考えよう。
その矩形を切断する線がX本あるとする。

紙を切断したら、指定マスがない方を捨てるのではなく、捨てずに全ラインをランダムな順で選ぶという手順を考えよう。
この矩形の左側にある線を考える。
矩形から見てY本目の線だとする。
全ラインをランダムで選んだ時、このラインにより紙の切断が生じる確率は1/(X+Y)である。
よって解には1/(X+Y)だけ計上される。

同様に、指定2マスを囲う矩形外のラインについて、上記切断により解に計上される確率の総和を求めればよい。

int H,W;
int Y[2],X[2];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	cin>>Y[0]>>X[0]>>Y[1]>>X[1];
	
	int A=min(X[0],X[1])-1;
	int B=W-max(X[0],X[1]);
	int C=min(Y[0],Y[1])-1;
	int D=H-max(Y[0],Y[1]);
	int E=abs(X[0]-X[1])+abs(Y[0]-Y[1]);
	
	ll ret=1;
	for(i=1;i<=A;i++) ret+=modpow(i+E);
	for(i=1;i<=B;i++) ret+=modpow(i+E);
	for(i=1;i<=C;i++) ret+=modpow(i+E);
	for(i=1;i<=D;i++) ret+=modpow(i+E);
	
	cout<<ret%mo<<endl;
	
}

まとめ

本番組み合わせ論的に数えようとしたのが失敗だった。
Cも似たようなアイデアだったのになぜこちらに考えが至らなかったのか…。