結果

問題 No.658 テトラナッチ数列 Hard
ユーザー HaarHaar
提出日時 2018-09-26 09:24:55
言語 Haskell
(9.8.2)
結果
AC  
実行時間 1,348 ms / 2,000 ms
コード長 1,440 bytes
コンパイル時間 4,795 ms
コンパイル使用メモリ 190,336 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2024-04-17 15:31:18
合計ジャッジ時間 11,145 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,504 KB
testcase_03 AC 8 ms
8,192 KB
testcase_04 AC 441 ms
8,320 KB
testcase_05 AC 512 ms
8,320 KB
testcase_06 AC 654 ms
8,192 KB
testcase_07 AC 697 ms
8,448 KB
testcase_08 AC 899 ms
8,320 KB
testcase_09 AC 1,348 ms
8,704 KB
testcase_10 AC 1,328 ms
8,448 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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

ソースコード

diff # 

import Data.List
import Data.Int
import Control.Monad
import Control.Applicative
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

data Vector a = RVector [a] | CVector [a] deriving Show
newtype Matrix a = Matrix {getMatrix :: [[a]]} deriving Show

{-# INLINE mmap #-}
mmap f (Matrix a) = Matrix $ map (map f) a

{-# INLINE (|*|) #-}
(|*|) :: Num a => Matrix a -> Matrix a -> Matrix a
(|*|) (Matrix a) (Matrix b) = Matrix $ map (\va -> map (\vb -> sum $ zipWith (*) va vb) (transpose b)) a

{-# INLINE (|^:) #-}
(|^:) :: (Integral a , Integral b) => Matrix a -> (b, a) -> Matrix a
(|^:) (Matrix a) (0,_) = unitMatrix $ length a
(|^:) mat (1,_) = mat
(|^:) mat (p,m) = mmap (`mod` m) (if even p then t |*| t else t |*| t |*| mat)
  where t = mat |^: (div p 2, m)

{-# INLINE unitMatrix #-}
unitMatrix :: Num a => Int -> Matrix a
unitMatrix n = Matrix $ [[if i==j then 1 else 0 | j<-[1..n]] | i<-[1..n]]

{-# INLINE (|*!) #-}
(|*!) :: Num a => Matrix a -> Vector a -> Vector a
(|*!) (Matrix a) (CVector v) = CVector $ map (\r -> sum $ zipWith (*) r v) a

tetranacci 1 = 0
tetranacci 2 = 0
tetranacci 3 = 0
tetranacci 4 = 1
tetranacci n = let (CVector [x,_,_,_]) = (Matrix [[1,1,1,1],[1,0,0,0],[0,1,0,0],[0,0,1,0]]) |^: (n-4,17) |*! (CVector [1,0,0,0]) in x

main = do
  q <- readLn :: IO Int

  mapM_ print =<< do
    map (tetranacci . fromIntegral . fst . fromJust . BS.readInteger) . BS.lines <$> BS.getContents :: IO [Int64]
0