結果

問題 No.658 テトラナッチ数列 Hard
コンテスト
ユーザー Haar
提出日時 2018-09-26 09:24:55
言語 Haskell
(9.10.1)
結果
AC  
実行時間 1,406 ms / 2,000 ms
コード長 1,440 bytes
コンパイル時間 5,629 ms
コンパイル使用メモリ 190,208 KB
実行使用メモリ 8,704 KB
最終ジャッジ日時 2024-10-09 09:33:28
合計ジャッジ時間 12,586 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
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