Problem 237

237 Tours on a 4 x n playing board

Problem 237 – Project Euler

4×Nのタイルの巡り方の総数を求める問題.

どうせ,DPだよ,とか思っていた.

そこで,DPを構成するために,とりあえず,4×Nのタイルを4×1のタイルに分割して「状態」を考えることにした.

DPを構成するとき,どう,状態をとらえるか,が結構難しいわけだが…

タイルに描かれる,道を状態として考えることにしたら,うまくいった.

イメージとしては,線路をひくようなかんじ.

結論としては,4×1のタイルには,5つの道の描かれ方がある(端を除く).

しかし,巡り方(順序)も考慮すると,7つの状態がある(と思う,うまくすれば,もっと少ないかも).

各状態の遷移関係を考えると,過去は無関係に遷移することが分かった(あたりまえと言えば,あたりまえか?).

ってことで,結局は遷移行列の累乗を計算すれば良いことが分かった.

なので,計算量は非常に大雑把に見積って log N ぐらい.

これは,Haskellでも一瞬なれべるだ.

import Data.List (transpose)
type Matrix a = [[a]]
dim :: Matrix a -> (Int, Int)
dim (x:xs) = (length $ x:xs, length x)
dot :: (Num a) => [a] -> [a] -> a
dot x y = sum $ zipWith (*) x y
mulMod :: (Integral a) => a -> Matrix a -> Matrix a -> Matrix a
mulMod p a b = take m.map (take n).iterate (drop n).map ((x:y:_) -> mod (dot x y) p) $ sequence [a, transpose b]
where (m,_) = dim a
(n,_) = dim b
powMod :: (Integral a, Integral b) => a -> Matrix a -> b -> Matrix a
powMod p a n | n ==  = unit m
| even n = powMod p (mulMod p a a) (div n 2)
| otherwise = mulMod p a $ powMod p a (n-1)
where (m,_) = dim a
unit n = take n.map (take n).iterate (:) $ 1: repeat 
p237 :: (Integral t) => Integer -> t -> Integer
p237 p (n+3) = (`mod` p).sum.concat $ mulMod p (powMod p t n) s0
where s0 = map return [1,,,1,1,1,]
t = [[1,,,,,,1],
[,1,,1,,,],
[,,1,,,1,],
[1,,,,,,1],
[,,,,,,1],
[1,,,,,,1],
[,1,1,1,1,1,]]
main :: IO ()
main = print $ p237 (10 ^ 8) (10 ^ 12)

追記

RNさんのコメントから,

p237 :: (Integral t) => Integer -> t -> Integer
p237 p (n+2) = (`mod` p).sum.take 2.concat $ mulMod p (powMod p t n) s0
where s0 = map return [1,,,1]
t = [[1,1,,],
[2,,1,1],
[2,,1,],
[,1,,]]

行列は 4×4で十分.

あと,『タイルに描かれる,道を状態として考える』とか,上に書いてあるけど,

『右のタイルとの道のつながり方を状態として考える』のほうが正確な気がする.

More Reading
Newer// mail forward
Older// Problem 236