Document

Ｆ
１０歳の動的計画
原案：吉里
解答作成：吉里、渡部
解説：吉里
問題（要約）
(0,0)から(N,M)まで（1≦N,M≦100,000）
→(+1,0),↑(0,+1),←(-1,0),↓(0,-1)の
４種類の動きを組み合わせて移動する。
移動のしかたは何通りあるか。
10億7（素数）で割った余りを答えよ。
ただし、←(-1,0),↓(0,-1)を合計
ちょうどK回（1≦K≦10,000）使うこと
K回使い切る前に(N,M)にたどりついても
ゴールしたとみなさず動き続ける。
（X座標またはY座標が負の点に入るような移動はできない）
想定解法１/６
条件：←(-1,0),↓(0,-1)を合計K回使う
←を使う回数で場合分けして、全部足す。
←をp回、↓をK-p回使う、とする。
（p=0,1,2,……,K-1,Kについて和をとる）
想定解法２/６
X方向の移動とY方向の移動は
それぞれ独立に考えたうえで
あとで統合すればよい。
（←→計a個を並べる場合の数）
×（↑↓計b個を並べる場合の数）
×(a+b)Ｃa
想定解法３/６
・残された問題
→N+p個と←p個を並べる
（ex.→←→→←←……）
ただし、X座標が負の点には入れない
（∀i, ←がi回出る前に→がi回以上出る）
この「ただし」をどう扱うか？
想定解法４/６
→か↑に進んで、Ｓ⇒Ｇを目指す問題を考える
「Ｓ⇒Ｇの、赤丸を通らないルートの総数」
＝「Ｓ⇒Ｇのルートの総数」－
「Ｓ⇒Ｇの、赤丸を通るルートの総数」
＝「Ｓ⇒Ｇのルートの総数」－
「Ｓ⇒Ｇ’のルートの総数」
想定解法５/６
「初めて赤丸を通った点」に注目して、
以後、反転した動きをすれば
Ｇの代わりにＧ’に着く
想定解法６/６
→N+p個と←p個を
「←がi回出る前に→がi回以上出る」
ように並べる場合の数
＝ (N+2p)Ｃp × (N+1)/(N+p+1)
コンビネーションの値は
p=iの値があればp=i+1の値計算はO(1)
補足
MOD.p（pは素数）の世界では、
(÷a)と、(×a^{p-2})は等価
（証明）
フェルマーの小定理(aとpは互いに素)
a^{p-1}≡1 (mod.p) (pは素数)
a^{p-2}は、繰り返し二乗法でO(logp).

Download Report