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 == 0 = 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 (0:) $ 1: repeat 0

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,0,0,1,1,1,0]
          t = [[1,0,0,0,0,0,1],
               [0,1,0,1,0,0,0],
               [0,0,1,0,0,1,0],
               [1,0,0,0,0,0,1],
               [0,0,0,0,0,0,1],
               [1,0,0,0,0,0,1],
               [0,1,1,1,1,1,0]]

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,0,0,1]
          t = [[1,1,0,0],
               [2,0,1,1],
               [2,0,1,0],
               [0,1,0,0]]

行列は 4×4で十分．
あと，『タイルに描かれる，道を状態として考える』とか，上に書いてあるけど，
『右のタイルとの道のつながり方を状態として考える』のほうが正確な気がする．