Submission #4147694


Source Code Expand

Copy
{-# LANGUAGE BangPatterns #-}
import Data.Int (Int64)
import qualified Data.Vector.Unboxed as V
import Data.List (foldl',tails)

modulo = 1000000007 :: Int64
addMod x y = (x + y) `mod` modulo
mulMod x y = (x * y) `mod` modulo
sumMod = foldl' addMod 0

-- 多項式は
--   V.fromList [a,b,c,...,z] = a + b * X + c * X^2 + ... + z * X^(k-1)
-- により表す。

-- 多項式を X^k - X^(k-1) - ... - X - 1 で割った余りを返す。
reduce :: Int -> V.Vector Int64 -> V.Vector Int64
reduce k v | V.last v == 0 = V.init v
           | V.length v <= k = v
           | otherwise = let b = V.last v
                             l = V.length v
                         in reduce k (V.imap (\i a -> if i >= l - k - 1 then a `addMod` b else a) (V.init v))

-- 多項式の積を X^k - X^(k-1) - ... - X - 1 で割った余りを返す。
mulP :: Int -> V.Vector Int64 -> V.Vector Int64 -> V.Vector Int64
mulP k !v !w = reduce k $ V.generate (V.length v + V.length w - 1) $
               \i -> sumMod [(v V.! (i-j)) `mulMod` (w V.! j) | j <- [0..V.length w-1], j <= i, j > i - V.length v]

-- 不定元
ind :: V.Vector Int64
ind = V.fromList [0,1]

-- 多項式の(mod X^k - X^(k-1) - ... - X - 1 での)べき乗
powP :: Int -> V.Vector Int64 -> Int -> V.Vector Int64
powP k _ 0 = V.fromList [1]
powP k m i = loop (i-1) m m
  where
    loop 0 !_ !acc = acc
    loop 1 m acc = mulP k m acc
    loop i m acc = case i `quotRem` 2 of
                     (j,0) -> loop j (mulP k m m) acc
                     (j,_) -> loop j (mulP k m m) (mulP k acc m)

main :: IO ()
main = do
  l <- getLine
  let [(k, l')] = (reads :: ReadS Int) l
      [(n, _)] = (reads :: ReadS Int) l'
  if n <= k
    then print 1
    else do
    let f = powP k ind (n - k) -- X^(n-k) mod X^k - X^(k-1) - ... - X - 1
    let seq = replicate k 1 ++ map (sumMod . take k) (tails seq) -- 数列
    print $ sumMod $ zipWith mulMod (V.toList f) (drop (k-1) seq)

Submission Info

Submission Time
Task T - フィボナッチ
User mod_poppo
Language Haskell (GHC 7.10.3)
Score 8
Code Size 1984 Byte
Status AC
Exec Time 1759 ms
Memory 2172 KB

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 1724 ms 2172 KB
01 AC 951 ms 1916 KB
02 AC 1759 ms 2172 KB
03 AC 294 ms 1916 KB
04 AC 2 ms 508 KB
90 AC 2 ms 508 KB
91 AC 2 ms 508 KB