結果
問題 | No.44 DPなすごろく |
ユーザー |
![]() |
提出日時 | 2019-08-26 14:12:01 |
言語 | Haskell (9.10.1) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 816 bytes |
コンパイル時間 | 9,415 ms |
コンパイル使用メモリ | 171,392 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 18:57:51 |
合計ジャッジ時間 | 2,973 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-} data Matrix a = Matrix2x2 !a !a !a !a matMul :: Matrix Integer -> Matrix Integer -> Matrix Integer matMul (Matrix2x2 a b c d) (Matrix2x2 x y z w) = Matrix2x2 (a * x + b * z) (a * y + b * w) (c * x + d * z) (c * y + d * w) matPower :: Matrix Integer -> Int -> Matrix Integer matPower _ 0 = Matrix2x2 1 0 0 1 matPower m i = loop m m (i - 1) where loop acc !_ 0 = acc loop acc m 1 = acc `matMul` m loop acc m i = case i `divMod` 2 of (j, 0) -> loop acc (m `matMul` m) j (j, _) -> loop (acc `matMul` m) (m `matMul` m) j main :: IO () main = readLn >>= print . solve solve :: Int -> Integer solve m = let (Matrix2x2 a b c d) = (Matrix2x2 1 1 1 0) `matPower` (m + 1) in b