結果
問題 | No.2007 Arbitrary Mod (Easy) |
ユーザー | sanao10000 |
提出日時 | 2022-07-15 22:02:02 |
言語 | Haskell (9.8.2) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 4,863 bytes |
コンパイル時間 | 12,247 ms |
コンパイル使用メモリ | 234,252 KB |
実行使用メモリ | 7,360 KB |
最終ジャッジ日時 | 2023-09-10 01:52:47 |
合計ジャッジ時間 | 14,201 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
7,240 KB |
testcase_01 | AC | 3 ms
7,172 KB |
testcase_02 | AC | 2 ms
7,268 KB |
testcase_03 | AC | 3 ms
7,252 KB |
testcase_04 | AC | 3 ms
7,256 KB |
testcase_05 | AC | 3 ms
7,196 KB |
testcase_06 | AC | 2 ms
7,196 KB |
testcase_07 | AC | 3 ms
7,184 KB |
testcase_08 | AC | 3 ms
7,200 KB |
testcase_09 | AC | 3 ms
7,200 KB |
testcase_10 | AC | 3 ms
7,256 KB |
testcase_11 | AC | 3 ms
7,360 KB |
testcase_12 | AC | 2 ms
7,264 KB |
testcase_13 | AC | 3 ms
7,308 KB |
testcase_14 | AC | 2 ms
7,200 KB |
testcase_15 | AC | 2 ms
7,272 KB |
testcase_16 | AC | 3 ms
7,220 KB |
testcase_17 | AC | 2 ms
7,192 KB |
testcase_18 | AC | 2 ms
7,200 KB |
testcase_19 | AC | 2 ms
7,180 KB |
testcase_20 | AC | 3 ms
7,252 KB |
testcase_21 | AC | 2 ms
7,232 KB |
testcase_22 | AC | 2 ms
7,272 KB |
testcase_23 | AC | 2 ms
7,192 KB |
testcase_24 | AC | 2 ms
7,268 KB |
testcase_25 | AC | 3 ms
7,204 KB |
testcase_26 | AC | 3 ms
7,180 KB |
testcase_27 | AC | 2 ms
7,308 KB |
testcase_28 | AC | 3 ms
7,256 KB |
testcase_29 | AC | 3 ms
7,192 KB |
testcase_30 | AC | 2 ms
7,200 KB |
testcase_31 | AC | 2 ms
7,204 KB |
testcase_32 | AC | 2 ms
7,192 KB |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns , BlockArguments ,FlexibleContexts ,FlexibleInstances ,OverloadedStrings ,TypeApplications ,MultiParamTypeClasses ,TupleSections #-} {-# OPTIONS_GHC -Wno-missing-methods #-} {-# OPTIONS_GHC -Wno-unrecognised-pragmas #-} import Control.Monad (replicateM,forM_,when,(<=<)) import Data.Maybe (fromJust) import Data.Array.IO(IOUArray,IOArray) import Data.Array.Unboxed(UArray,Ix) import qualified Data.Array.MArray as MA import qualified Data.Array.IArray as A import qualified Data.ByteString.Char8 as BS import qualified Data.Set as S import qualified Data.Map as Map import qualified Data.Sequence as Seq import Data.STRef import Data.Array.ST import Control.Monad.ST import qualified Data.IntMap as IM import qualified Data.Map.Strict as Map import Data.List(sort, intersperse,permutations) import Control.Monad.State import qualified Data.Foldable as F import Data.IORef import Data.Foldable (traverse_) -- ================================================================== powMod :: Int -> Int -> Int -> Int powMod a n m = go a n where go !x !n' | n' == 0 = 1 | even n' = let !y = go x (n' `div` 2) in y*y `mod` m | otherwise = let !y = go x (n' - 1) in x*y `mod` m main :: IO () main = do [a, n]<- input @[Int] let m = 998244353 in print m >> print (powMod a n m) -- ================================================================== swapArray :: (MA.MArray a e m, Ix i) => a i e -> i -> i -> m () swapArray a i j = do ai <- MA.readArray a i aj <- MA.readArray a j MA.writeArray a i aj MA.writeArray a j ai initUG :: Int -> [[Int]] -> A.Array Int [Int] initUG n xs = A.accumArray (flip (:)) [] (0, n-1) $ concatMap (\[a, b] -> [(a, b), (b, a)]) xs seqfront :: Seq.ViewL a -> a seqfront(a Seq.:< b) = a seqpop :: Seq.ViewL a -> Seq.Seq a seqpop(a Seq.:< b) = b modifyArray :: (MA.MArray a e m, Ix i) => a i e -> i -> (e -> e) -> m () modifyArray !a !i !f = MA.writeArray a i . f =<< MA.readArray a i {-# INLINE modifyArray #-} type Bs = BS.ByteString type Height = Int type Width = Int type MutableArray2D any = IOUArray (Height,Width) any type Array2D any = UArray (Height, Width) any -- 初期化DP配列==================================================== class DPArray a where initDP :: Height -> Width -> a -> IO(MutableArray2D a) instance DPArray Int where initDP = ((MA.newArray . ((0, 0) ,)) .) . (. subtract 1) . (,) . subtract 1 instance DPArray Double where initDP = ((MA.newArray . ((0, 0) ,)) .) . (. subtract 1) . (,) . subtract 1 instance DPArray Bool where initDP = ((MA.newArray . ((0, 0) ,)) .) . (. subtract 1) . (,) . subtract 1 -- ================================================================= -- 入力 ===================================================================================================================================================== class (Read a) => Input a where read' :: BS.ByteString -> a readArray2D :: Height -> Width -> BS.ByteString -> a input :: Input a => IO a input = read' <$> BS.getLine inputs :: Input a => IO a inputs = read' <$> BS.getContents inputArray :: Input a => Int -> Int -> IO a inputArray = flip flip BS.getContents . ((<$>) .) . readArray2D instance Input Bs where read' = id instance Input Int where read' = fst . fromJust . BS.readInt instance Input Integer where read' = (read @Integer) . BS.unpack instance Input Double where read' = read . BS.unpack instance Input [Bs] where read' = BS.words instance Input [Int] where read' = map (fst . fromJust . BS.readInt) . BS.words instance Input [Double] where read' = map ((read @Double) . BS.unpack) . BS.words instance Input [(Int, Bs)] where read' = map ((\[a, b] -> (fst (fromJust (BS.readInt a)), b)) . BS.words) . BS.lines instance Input [(Bs, Int)] where read' = map ((\[a, b] -> (a, fst (fromJust (BS.readInt b)))) . BS.words) . BS.lines instance Input [[Bs]] where read' = map BS.words . BS.lines instance Input [[Int]] where read' = map (map (fst . fromJust . BS.readInt) . BS.words) . BS.lines instance Input [[Double]] where read' = map (map ( (read @Double) . BS.unpack) . BS.words) . BS.lines instance Input (Array2D Int) where readArray2D = flip flip ((map (fst . fromJust . BS.readInt) . BS.words) <=< BS.lines) . (((.) . A.listArray . ((0, 0) ,)) .) . (. subtract 1) . (,) . subtract 1 instance Input (Array2D Double) where readArray2D height width = A.listArray ((0, 0), (height - 1, width - 1)) . concatMap (map ((read @Double) . BS.unpack) . BS.words) . BS.lines instance Input (Array2D Char) where readArray2D = flip flip (BS.unpack <=< BS.lines) . (((.) . A.listArray . ((0, 0) ,)) .) . (. subtract 1) . (,) . subtract 1 -- ============================================================================================================================================================