Contest Duration: - (local time) (100 minutes) Back to Home

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
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
let m = matPow 7 mat n
print \$ m ! (1,1)
```

#### Submission Info

Submission Time 2019-03-25 18:45:05+0900 D - We Like AGC mod_poppo Haskell (GHC 7.10.3) 400 1942 Byte AC 2 ms 508 KB

#### Judge Result

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