ARC058 D-いろはちゃんとマス目

【問題】
arc058.contest.atcoder.jp

【考察】
典型数え上げ問題の変形タイプ。この問題では少し特殊な制約がついていて、二項係数ライブラリで一発 AC というわけにはいきません。まず数え上げ問題の常套手段として、いくつかの排反な事象への場合分けをします。この場合分けのやり方は色々あると思うんですが、自分の場合は、

「このピンクで囲まれたマス (まとめて P とします) のうち、初めて到達するマスがどれであるか」で場合分けをしました。この場合分けは明らかに排反なものになっていますし、ゴールまでの経路は必ず P のうち少なくとも 1 つの点を通るため、この場合分けで全ての経路を数え上げることができます。P のうち上から i マス目 (点 p とする) を初めて訪れる経路の数を考えてみます。ここで、p までのある移動経路について最後の移動が下方向だった場合、その経路は P のうちの初めて訪れるマスが p ではありません。つまり、ある経路が P のうち初めて通るマスが p であるためには、p までの移動経路の最後の 1 回の移動は右方向である必要があります (逆に最後の 1 回の移動が右方向であれば、そのような経路は P のうち初めて通るマスが p となります)。あとは典型問題で、各 p ごとに p までの (P のうち初めて通るマスが p になるような) 経路数 * p からゴールまでの経路数を足していけばよいです。

【コード】

// 二項係数ライブラリは省略。mod_comb(n, k) が nCk に相当。
int main() {
	int h,w,a,b;
	cin>>h>>w>>a>>b;
	ll res=0;
	REP(i,h-a) {
		res+=mod_comb(b-1+i,b-1)*mod_comb(w-b-1+(h-1-i),w-b-1);
		res%=MOD;
	}
	cout<<res<<endl;
}

【使ったアイデア】
数え上げ問題における、排反事象への場合分け。二項係数の高速な計算。

【得た知見】
数え上げ問題は、何を基準に場合分けするかが肝心。