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で十分．

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

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