結果
問題 | No.980 Fibonacci Convolution Hard |
ユーザー | こまる |
提出日時 | 2020-11-21 00:25:39 |
言語 | Haskell (9.8.2) |
結果 |
AC
|
実行時間 | 216 ms / 2,000 ms |
コード長 | 6,936 bytes |
コンパイル時間 | 10,730 ms |
コンパイル使用メモリ | 265,216 KB |
実行使用メモリ | 29,952 KB |
最終ジャッジ日時 | 2024-07-23 14:10:39 |
合計ジャッジ時間 | 18,375 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 161 ms
29,800 KB |
testcase_01 | AC | 210 ms
29,824 KB |
testcase_02 | AC | 204 ms
29,824 KB |
testcase_03 | AC | 185 ms
29,696 KB |
testcase_04 | AC | 203 ms
29,824 KB |
testcase_05 | AC | 216 ms
29,824 KB |
testcase_06 | AC | 178 ms
29,824 KB |
testcase_07 | AC | 178 ms
29,952 KB |
testcase_08 | AC | 176 ms
29,952 KB |
testcase_09 | AC | 171 ms
29,824 KB |
testcase_10 | AC | 185 ms
29,824 KB |
testcase_11 | AC | 189 ms
29,696 KB |
testcase_12 | AC | 173 ms
29,952 KB |
testcase_13 | AC | 177 ms
29,824 KB |
testcase_14 | AC | 182 ms
29,824 KB |
testcase_15 | AC | 176 ms
29,824 KB |
testcase_16 | AC | 146 ms
29,568 KB |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default Main.hs:9:14: warning: [GHC-53692] [-Wdeprecated-flags] -XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead | 9 | {-# LANGUAGE TypeInType #-} | ^^^^^^^^^^ [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE TypeInType #-} {-# LANGUAGE UnboxedTuples #-} import Control.Monad.State import Data.Bits import Data.Char import Data.Coerce import qualified Data.Ratio as R import GHC.Exts import Unsafe.Coerce import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Generic as VG import qualified Data.Vector.Generic.Mutable as VGM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM #define MOD 1000000007 main :: IO () main = do p <- readLn :: IO Mint query <- readLn :: IO Int qs <- parseN1 query dp <- VUM.unsafeNew 2000001 :: IO (VUM.IOVector Mint) VUM.unsafeWrite dp 0 0 VUM.unsafeWrite dp 1 0 VUM.unsafeWrite dp 2 1 VUM.unsafeWrite dp 3 (2 * mint p) range 4 2000000 $ \i -> do item1 <- VUM.unsafeRead dp (i - 1) item2 <- VUM.unsafeRead dp (i - 2) item3 <- VUM.unsafeRead dp (i - 3) item4 <- VUM.unsafeRead dp (i - 4) VUM.unsafeWrite dp i (2 * p * item1 - (p * p - 2) * item2 - 2 * p * item3 - item4) rep query $ \i -> print =<< VUM.unsafeRead dp (qs VU.! i - 2) rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (streamG 0 (n - 1) const 0 (+) 1) {-# INLINE rep #-} range :: Monad m => Int -> Int -> (Int -> m ()) -> m () range l r = flip VFSM.mapM_ (streamG l r const 0 (+) 1) {-# INLINE range #-} streamG :: Monad m => Int -> Int -> (Int -> Int -> Int) -> Int -> (Int -> Int -> Int) -> Int -> VFSM.Stream m Int streamG !l !r !f !p !g !d = VFSM.Stream step l where step x | f x p <= r = return $ VFSM.Yield x (g x d) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamG #-} type CParser a = StateT BSC8.ByteString Maybe a runCParser :: CParser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString) runCParser = runStateT {-# INLINE runCParser #-} int :: CParser Int int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace {-# INLINE int #-} parseN1 :: Int -> IO (VU.Vector Int) parseN1 n = VU.unfoldrN n (runCParser int) <$> BSC8.getContents {-# INLINE parseN1 #-} modulus :: Num a => a modulus = MOD {-# INLINE modulus #-} infixr 8 ^% infixl 7 *%, /% infixl 6 +%, -% (+%) :: Int -> Int -> Int (I# x#) +% (I# y#) = case x# +# y# of r# -> I# (r# -# ((r# >=# MOD#) *# MOD#)) {-# INLINE (+%) #-} (-%) :: Int -> Int -> Int (I# x#) -% (I# y#) = case x# -# y# of r# -> I# (r# +# ((r# <# 0#) *# MOD#)) {-# INLINE (-%) #-} (*%) :: Int -> Int -> Int (I# x#) *% (I# y#) = case timesWord# (int2Word# x#) (int2Word# y#) of z# -> case timesWord2# z# im# of (# q#, _ #) -> case minusWord# z# (timesWord# q# m#) of v# | isTrue# (geWord# v# m#) -> I# (word2Int# (plusWord# v# m#)) | otherwise -> I# (word2Int# v#) where m# = int2Word# MOD# im# = plusWord# (quotWord# 0xffffffffffffffff## m#) 1## {-# INLINE (*%) #-} (/%) :: Int -> Int -> Int (I# x#) /% (I# y#) = go# y# MOD# 1# 0# where go# a# b# u# v# | isTrue# (b# ># 0#) = case a# `quotInt#` b# of q# -> go# b# (a# -# (q# *# b#)) v# (u# -# (q# *# v#)) | otherwise = I# ((x# *# (u# +# MOD#)) `remInt#` MOD#) {-# INLINE (/%) #-} (^%) :: Int -> Int -> Int x ^% n | n > 0 = go 1 x n | n == 0 = 1 | otherwise = go 1 (1 /% x) (-n) where go !acc !y !m | m .&. 1 == 0 = go acc (y *% y) (unsafeShiftR m 1) | m == 1 = acc *% y | otherwise = go (acc *% y) (y *% y) (unsafeShiftR (m - 1) 1) newtype Mint = Mint { getMint :: Int } deriving newtype (Eq, Ord, Read, Show, Real) mint :: Integral a => a -> Mint mint x = fromIntegral $ mod (fromIntegral x) MOD {-# INLINE mint #-} mintValidate :: Mint -> Bool mintValidate (Mint x) = 0 <= x && x < MOD {-# INLINE mintValidate #-} instance Bounded Mint where minBound = Mint 0 maxBound = Mint $ modulus - 1 instance Enum Mint where toEnum = mint fromEnum = coerce instance Integral Mint where quotRem x y = (x / y, x - x / y * y) toInteger = coerce (toInteger @Int) instance Num Mint where (+) = coerce (+%) (-) = coerce (-%) (*) = coerce (*%) abs = id signum = const (Mint 1) fromInteger x = coerce @Int @Mint . fromInteger $ mod x modulus instance Fractional Mint where (/) = coerce (/%) fromRational q = fromInteger (R.numerator q) / fromInteger (R.denominator q) newtype instance VUM.MVector s Mint = MV_Mint (VUM.MVector s Int) newtype instance VU.Vector Mint = V_Mint (VU.Vector Int) instance VU.Unbox Mint instance VGM.MVector VUM.MVector Mint where basicLength (MV_Mint v) = VGM.basicLength v {-# INLINE basicLength #-} basicUnsafeSlice i n (MV_Mint v) = MV_Mint $ VGM.basicUnsafeSlice i n v {-# INLINE basicUnsafeSlice #-} basicOverlaps (MV_Mint v1) (MV_Mint v2) = VGM.basicOverlaps v1 v2 {-# INLINE basicOverlaps #-} basicUnsafeNew n = MV_Mint `fmap` VGM.basicUnsafeNew n {-# INLINE basicUnsafeNew #-} basicInitialize (MV_Mint v) = VGM.basicInitialize v {-# INLINE basicInitialize #-} basicUnsafeReplicate n x = MV_Mint `fmap` VGM.basicUnsafeReplicate n (coerce x) {-# INLINE basicUnsafeReplicate #-} basicUnsafeRead (MV_Mint v) i = coerce `fmap` VGM.basicUnsafeRead v i {-# INLINE basicUnsafeRead #-} basicUnsafeWrite (MV_Mint v) i x = VGM.basicUnsafeWrite v i (coerce x) {-# INLINE basicUnsafeWrite #-} basicClear (MV_Mint v) = VGM.basicClear v {-# INLINE basicClear #-} basicSet (MV_Mint v) x = VGM.basicSet v (coerce x) {-# INLINE basicSet #-} basicUnsafeCopy (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeCopy v1 v2 {-# INLINE basicUnsafeCopy #-} basicUnsafeMove (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeMove v1 v2 {-# INLINE basicUnsafeMove #-} basicUnsafeGrow (MV_Mint v) n = MV_Mint `fmap` VGM.basicUnsafeGrow v n {-# INLINE basicUnsafeGrow #-} instance VG.Vector VU.Vector Mint where basicUnsafeFreeze (MV_Mint v) = V_Mint `fmap` VG.basicUnsafeFreeze v {-# INLINE basicUnsafeFreeze #-} basicUnsafeThaw (V_Mint v) = MV_Mint `fmap` VG.basicUnsafeThaw v {-# INLINE basicUnsafeThaw #-} basicLength (V_Mint v) = VG.basicLength v {-# INLINE basicLength #-} basicUnsafeSlice i n (V_Mint v) = V_Mint $ VG.basicUnsafeSlice i n v {-# INLINE basicUnsafeSlice #-} basicUnsafeIndexM (V_Mint v) i = coerce `fmap` VG.basicUnsafeIndexM v i {-# INLINE basicUnsafeIndexM #-} basicUnsafeCopy (MV_Mint mv) (V_Mint v) = VG.basicUnsafeCopy mv v elemseq _ = seq {-# INLINE elemseq #-}