結果
問題 |
No.526 フィボナッチ数列の第N項をMで割った余りを求める
|
ユーザー |
![]() |
提出日時 | 2019-08-23 00:12:10 |
言語 | Haskell (9.10.1) |
結果 |
AC
|
実行時間 | 207 ms / 2,000 ms |
コード長 | 897 bytes |
コンパイル時間 | 1,831 ms |
コンパイル使用メモリ | 170,240 KB |
実行使用メモリ | 14,696 KB |
最終ジャッジ日時 | 2024-10-13 07:19:40 |
合計ジャッジ時間 | 3,271 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
コンパイルメッセージ
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 = Matrix !a !a !a !a matrixMul :: Num a => Matrix a -> Matrix a -> Matrix a matrixMul (Matrix a b c d) (Matrix a' b' c' d') = Matrix (a * a' + b * c') (a * b' + b * d') (c * a' + d * c') (c * b' + d * d') matrixPow :: Num a => Matrix a -> Integer -> Matrix a matrixPow _ 0 = Matrix 1 0 0 1 matrixPow m i = loop m m (i - 1) where loop acc !_ 0 = acc loop acc m 1 = matrixMul acc m loop acc m i = case i `quotRem` 2 of (j, 0) -> loop acc (matrixMul m m) j (j, _) -> loop (matrixMul acc m ) (matrixMul m m) j fib :: Integer -> Integer fib i = let Matrix a b c d = matrixPow (Matrix 0 1 1 1) (i - 1) in b main :: IO () main = interact $ show . solve . map (read :: String -> Integer) . words solve :: [Integer] -> Integer solve [n, m] = ( fib n ) `mod` m