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

D いろはちゃんとマス目

所見

高校数学。

問題概要

H*Wの座標平面がある。 左上のマス目から右下のマス目まで最短経路で移動する方法のうち、下からA個以内、左からB個以内のマスに入らないものを求めよ。

取った方針

高校数学が世界一できないので高校数学フェーズでバグらせて終了
右上 -> 下からA個、左からB+i個(B+i<=W)目のマスの行き方 * 下からA個、左からB+i個(B+i<=W)目のマス -> 左下 の総和を求めると、下からA個、左からB+i個目のマス -> 左下 の道順と、下からA個、左からB+i+1個目のマス -> 左下の道順には重複がある(下からA個、左からB+i個目のマスから右に移動する場合)のでバグる。

正しい方針

重複させないためには、右上 -> 下からA+1個、左からB+i個(B+i<=W)目のマスの行き方 * 下からA個、左からB+i個(B+i<=W)目のマス -> 左下 の総和を求める。
下からA個、左からB+i個目のマスにはかならず上から入ることにすれば重複をなくして正しく数えることができる。
nCrは、n!/((n-r)! * r!) であるのでO(n)かけてn! までの階乗を計算しておけばO(1)で求まる。n<=H+Wなので、O(H+W)。
modの逆元は、拡張ユークリッドの互除法などを用いれば求めることができる。また、nまでの逆元を求めたい場合、拡張ユークリッドの互除法でnの逆元だけを計算し、あとはn, n-1, n-2...を順番に掛け算していけば高速に求めることができる。(logが消えるだけなので大差ないという見方もある)
これらをすべてやってくれる神ライブラリがlibalgoにあるので張り付けて上記の方針に基づいて計算すると解ける。

得られた知見

・nCrは漸化式でDPをすると時間O(nr)、空間O(nr)かかるが、nの階乗を事前計算するとO(n)で求めることができる。ただし、階乗は発散が速いので今回のようにmodを取る場合しか使えない。(modを取らない場合long long でn=20でオーバーフローする)
・modの逆元はユークリッドの互除法で求められる。
・階乗の(modの)逆元は最初にnの階乗を計算しておき、n, n-1, n-2...を順番に掛け算していくことで高速に求められる。
・これらをすべてやってくれるライブラリが公開されている。
・ただし、libalgoの実装ではMODULO > TABLE_SIZEでないと配列外参照で落ちるので注意する。(modulo以上の値が現れることはないのでそれはそう)

解くのに必要な要素

・高校数学(場合の数)
・高校数学(mod)
・modの逆元がユークリッドの互除法で求まること
・nCrはnまでの階乗をO(n)で事前計算しておくと高速に求められること(modを取る場合しか事実上有用ではない)

周辺調査によって得られた知見

・特になし