yukicoder No.660 家を通り過ぎないランダムウォーク問題

問題

東西にのびる1次元の道の原点に立っており、東にN歩のところに家がある。
2*N歩以下で家にたどり着くような歩き方を、10^9+7で割った余りで答えよ。
ただし、家に一度たどり着いたら必ず歩くのをやめて家にはいり、それ以降は歩かない。

制約

• 1<= N <= 2*10^5

解法

縦軸に位置、横軸に歩数をとって、移動を図にすると以下のようになっている。
(右下か右上にしか移動しない)

求めたい答えは、「(Aまでの経路数)＋(Bまでの経路数)＋(Cまでの経路数)＋・・・」になっている。

向きを45度回転させてみると、あるGまでの歩き方というのは以下のような右上部分がちょっとかけた経路数になっている。

この、SからGまで、下か右のみ移動できる場合の経路数を求めたい。

まず、右上が欠けていない経路を考える。

この場合、SからGまでの経路数は、縦がh、横がwの場合、「{h+w}_C_w」で求められる。
(右移動がw個、下移動がh個あって、{h+w}ステップの中で右移動の場所を決めてしまえば、残りが下移動になるため、そのような組み合わせの数になる)

次に、赤太線の部分を通る経路をここから引きたい。
図のように斜めの線を引いて、Gの位置が線対称となるようなところにGを設定した、以下のような図を考える。

この図でのSからGまでの経路は、必ず斜めの線をまたいでいて、ステップ数は{h+w}になっているので、赤線を1度は通った場合の経路数になっている。
(実際、斜めの線を超えた場合に「右移動を下移動」「下移動を右移動」に対応付けると実際の赤太線を1度は通る経路に対応づく)
この経路数は「{h-1+w+1}_C_{w+1}」で求められる。

したがって、右上が欠けたような経路数は「{h+w}_C_w - {h+w}_C_{w+1}」で求められるので、一番上の図のA,B,C.・・・すべてについて求めて足してあげればよい。

上記、mod_comb(n,m,MOD)を高速に求める必要がある。
予め、階乗を普通にforループとかで計算しておき、階乗の逆元はMODが素数なのでフェルマーの小定理から「a^{-1}=a^{MOD-2}」で求めておける(mod_powを使う)。
よって、「n_C_m = n! / (m! * (n-m)!)」は、求めておいた階乗と階乗の逆元から高速に求められる。

ちなみに、カタラン数は、h=w=nのケースで同様に考えれば、求められるので、「C_n = {2*n}_C_n - {2*n}_C_{n+1} = {2*n}_C_n - {2*n}_C_{n-1}」。