Problem 408 「格子間の許容経路」

x, y, そして x + y がすべて正の完全平方数であるとき, その格子点 (x, y) を非許容点と呼ぼう.
例えば, (9, 16) は非許容点であり, (0, 4), (3, 1), (9, 4) はそうではない.

点 (x&sub{1};, y&sub{1};) から (x&sub{2};, y&sub{2};) へ, 北か東への単位ステップのみを使って移動する経路を考えよう.
もしその経路の途中の点で非許容点を通らないとき, そのような経路を許容経路と呼ぼう.

(0, 0) から (n, n) までの許容経路の数を P(n) としよう.
P(5) = 252, P(16) = 596994440, P(1000) mod 1 000 000 007 = 341920854 であることが確かめられる.

P(10 000 000) mod 1 000 000 007 を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-12-29 (土) 23:17:37