Problem 289 「オイラー閉路」

C(x,y) を (x,y), (x,y+1), (x+1,y), (x+1, y+1) を通る円とする.

正の整数 m, n に対し, E(m,n) を以下のm⋅n の円からなる図形とする:
{C(x,y): 0≤x<m, 0≤y<n, xとyは整数}

E(m,n) 上のオイラー閉路とは, 全ての弧をちょうど1度ずつ通る経路のことである.
E(m,n) 上に多数のそのような経路があるが, ここでは自身と交わらないものだけを考える: 交差のない経路では格子点上で自身の経路に触れるが, 決して交差しない.

下の図は E(3,3) とその上の交差のないオイラー閉路の一例である.

p_289_euler.gif

L(m, n) を E(m, n) 上の交差のないオイラー閉路の数とする.
例えば, L(1,2)=2, L(2,2)=37, L(3,3)=104290 である.

L(6,10) mod 1010 を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-04-23 (金) 21:35:42 (2589d)