*[[Problem 502:http://projecteuler.net/problem=502]] 「城の数え上げ」 [#r2933992]

高さが 1, そして整数値の長さを持つ直方体からなる%%%ブロック%%%を定義しよう. そして積み重ねたブロックの配置を%%%城%%%と呼ぶことにする.

'''w''' の幅と '''h''' の高さを持つゲーム盤が与えられており, 城は以下のルールに従って生成される:

+ ブロックは端から飛び出たり空間に張り出したりすることがなければ, 他のブロックの上に配置することができる.
+ 全てのブロックはゲーム盤の格子に整列/スナップされていること.
+ 同じ段の近接する2つのブロックには少なくともその間に1単位分の空間がなければならない.
+ 最下段には '''w''' の長さのブロックが置かれている.
+ 城全体で最も積み上がっている部分の高さはぴったり '''h''' の高さである.
+ 城は偶数個のブロックによって作られる.

下記にあるのは '''w'''=8 そして '''h'''=5 のときの城の例である:

#ref(p502_castles.png,center,nolink)

格子の変数 '''w''', '''h''' が与えられた時の条件を満たす城の個数を F('''w''','''h''') で表すとしよう.

例として, F(4,2) = 10, F(13,10) = 3729050610636, F(10,13) = 37959702514, そして  F(100,100) mod 1 000 000 007 = 841913936.

(F(10&sup{12};,100) + F(10000,10000) + F(100,10&sup{12};)) mod 1 000 000 007 を求めよ.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS