Submission #4709903


Source Code Expand

Copy
{-# LANGUAGE BangPatterns #-}
import Data.Array.Unboxed
import Data.Ix (range)
import Data.Int (Int64)
import Data.List (foldl')

modulo = 1000000007 :: Int64
addMod x y = (x + y) `rem` modulo
mulMod x y = (x * y) `rem` modulo
sumMod = foldl' addMod 0
fromIntegerMod :: Integer -> Int64
fromIntegerMod x = fromInteger (x `mod` fromIntegral modulo)

---

matMul :: UArray (Int,Int) Int64 -> UArray (Int,Int) Int64 -> UArray (Int,Int) Int64
matMul a b = let ((i0,j0),(ix,jx)) = bounds a
                 ((j'0,k0),(j'x,kx)) = bounds b
             in if jx - j0 == j'x - j'0
                   then array ((i0,k0),(ix,kx))
                        [ ((i,k), sumMod [(a!(i,j)) `mulMod` (b!(j',k)) | (j,j') <- zip (range (j0,jx)) (range (j'0,j'x))])
                        | i <- range (i0,ix)
                        , k <- range (k0,kx)
                        ]
                else error "Matrix size mismatch"

matPow :: Int -> UArray (Int,Int) Int64 -> Int -> UArray (Int,Int) Int64
matPow k m 0 = array ((1,1),(k,k)) $
               [((i,j), if i == j then 1 else 0) | i <- [1..k], j <- [1..k]]
matPow _ m i = loop (i-1) m m
  where
    loop 0 !_ acc = acc
    loop 1 m acc = m `matMul` acc
    loop i m acc = case i `quotRem` 2 of
                     (j,0) -> loop j (m `matMul` m) acc
                     (j,_) -> loop j (m `matMul` m) (acc `matMul` m)

mat :: UArray (Int,Int) Int64
mat = array ((1,1),(7,7))
      [ ((i,j),aij)
      | (i,ai) <- zip [1..] values
      , (j,aij) <- zip [1..] ai
      ]
  where values = fmap (fmap fromIntegerMod)
          [[4, 0,-2,-3,-1, 0, 1]
          ,[1, 0, 0, 0, 0, 0, 0]
          ,[0, 1, 0, 0, 0, 0, 0]
          ,[0, 0, 1, 0, 0, 0, 0]
          ,[0, 1,-1, 0, 0, 0, 1]
          ,[0, 0, 0, 0, 1, 0, 0]
          ,[0, 0, 0, 0, 0, 1, 0]
          ]

main :: IO ()
main = do
  n <- readLn
  let m = matPow 7 mat n
  print $ m ! (1,1)

Submission Info

Submission Time
Task D - We Like AGC
User mod_poppo
Language Haskell (GHC 7.10.3)
Score 400
Code Size 1942 Byte
Status
Exec Time 2 ms
Memory 508 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 400 / 400 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13
Case Name Status Exec Time Memory
a01 2 ms 508 KB
a02 1 ms 508 KB
a03 2 ms 508 KB
b04 2 ms 508 KB
b05 2 ms 508 KB
b06 2 ms 508 KB
b07 2 ms 508 KB
b08 2 ms 508 KB
b09 2 ms 508 KB
b10 2 ms 508 KB
b11 2 ms 508 KB
b12 2 ms 508 KB
b13 2 ms 508 KB