Submission #171857


Source Code Expand

Copy
{-# LANGUAGE CPP #-}
#ifndef HDEVTOOLS
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
#endif
{-# LANGUAGE BangPatterns, ViewPatterns, OverloadedStrings #-}

import Control.Applicative
import qualified Data.ByteString.Char8 as S
import qualified Data.Vector.Unboxed as U

main :: IO ()
main = do
  _ <- getLine
  obss <- U.fromList . map readInt . S.words <$> S.getLine
  print $ unN $ solve obss

readInt :: S.ByteString -> Int
readInt s = case S.readInt s of
  Just (r, "") -> r
  _ -> error $ "not an integer: " ++ show s

solve :: U.Vector Int -> N
solve obss = (\(_, _, t) -> t) $ U.foldl' step (777, 0, 1) obss
  where
    step (!prev, !len, !total) (-1) = (prev, len+1, total)
    step (prev, len, total) obs = (obs, 0, total * choose (obs-prev+len) len)

newtype N = N {unN::Int}
  deriving (Show, Eq)

instance Num N where
  N a + N b = fromInt $ a + b
  N a - N b = fromInt $ a - b
  N a * N b = fromInt $ a * b
  fromInteger = fromInt . fromInteger
  abs = id
  signum = id

instance Fractional N where
  recip (N a) = fromInt $ fst $ egcd a modulus
  fromRational = error "fromRat"

_prop_fractional :: Int -> Int -> Bool
_prop_fractional a b = b ==0 || ( fromInt a / fromInt b * fromInt b == fromInt a)

egcd :: Int -> Int -> (Int, Int)
egcd _ 0 = (1, 0)
egcd a b = (x', y')
  where
    !x' = y
    !y' = x - (div a b) * y
    !(x, y) = egcd b (mod a b)

choose :: Int -> Int -> N
choose n k = prod [n-k+1 .. n] / prod [1..k]
  where
    prod = product . map N

fromInt :: Int -> N
fromInt k = N $ mod k modulus

modulus :: Int
modulus = 1000000007

Submission Info

Submission Time
Task C - タコヤ木
User mkotha
Language Haskell (GHC 7.4.1)
Score 100
Code Size 1623 Byte
Status AC
Exec Time 58 ms
Memory 1760 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 30 / 30 20 / 20
Status
AC × 3
AC × 14
AC × 26
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 27 ms 1116 KB
sample_02.txt AC 32 ms 1140 KB
sample_03.txt AC 29 ms 1056 KB
subtask1_01.txt AC 29 ms 1124 KB
subtask1_02.txt AC 29 ms 1284 KB
subtask1_03.txt AC 28 ms 1168 KB
subtask1_04.txt AC 30 ms 1240 KB
subtask1_05.txt AC 30 ms 1284 KB
subtask1_06.txt AC 28 ms 1180 KB
subtask1_07.txt AC 28 ms 1180 KB
subtask1_08.txt AC 30 ms 1240 KB
subtask1_09.txt AC 32 ms 1324 KB
subtask1_10.txt AC 29 ms 1296 KB
subtask1_11.txt AC 30 ms 1180 KB
subtask1_12.txt AC 58 ms 1232 KB
subtask2_01.txt AC 36 ms 1116 KB
subtask2_02.txt AC 31 ms 1252 KB
subtask2_03.txt AC 31 ms 1184 KB
subtask2_04.txt AC 32 ms 1564 KB
subtask2_05.txt AC 31 ms 1688 KB
subtask2_06.txt AC 31 ms 1760 KB
subtask2_07.txt AC 29 ms 1684 KB
subtask2_08.txt AC 31 ms 1692 KB
subtask2_09.txt AC 31 ms 1708 KB
subtask2_10.txt AC 32 ms 1688 KB
subtask2_11.txt AC 33 ms 1696 KB
subtask2_12.txt AC 33 ms 1636 KB
subtask3_01.txt AC 27 ms 1048 KB
subtask3_02.txt AC 27 ms 1264 KB
subtask3_03.txt AC 29 ms 1264 KB
subtask3_04.txt AC 34 ms 1628 KB
subtask3_05.txt AC 29 ms 1544 KB
subtask3_06.txt AC 29 ms 1760 KB
subtask3_07.txt AC 30 ms 1692 KB
subtask3_08.txt AC 28 ms 1688 KB
subtask3_09.txt AC 30 ms 1696 KB
subtask3_10.txt AC 31 ms 1696 KB
subtask3_11.txt AC 32 ms 1716 KB
subtask3_12.txt AC 32 ms 1696 KB