結果
問題 | No.1081 和の和 |
ユーザー |
![]() |
提出日時 | 2020-09-06 19:33:20 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 14,990 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 166,912 KB |
最終ジャッジ日時 | 2024-11-14 23:50:02 |
合計ジャッジ時間 | 685 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default Main.hs:25:14: warning: [GHC-53692] [-Wdeprecated-flags] -XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead | 25 | {-# LANGUAGE TypeInType #-} | ^^^^^^^^^^ [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:63:1: error: [GHC-61948] Could not find module ‘Data.ByteString.Lazy.Builder’. Perhaps you meant Data.ByteString.Builder (from bytestring-0.12.1.0) Data.ByteString.Lazy.Char8 (from bytestring-0.12.1.0) Data.ByteString.Lazy.ReadInt Use -v to see a list of the files searched for. | 63 | import qualified Data.ByteString.Lazy.Builder as BSLB | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:67:1: error: [GHC-87110] Could not load module ‘Data.Graph’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 67 | import qualified Data.Graph as Graph | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:68:1: error: [GHC-87110] Could not load module ‘Data.IntMap’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 68 | import Data.IntMap (IntMap) | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:69:1: error: [GHC-87110] Could not load module ‘Data.IntMap’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 69 | import qualified Data.IntMap as IntMap | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:70:1: error: [GHC-87110] Could not load module ‘Data.IntSet’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched fo
ソースコード
LANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGE---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------{- base -}importControl.ApplicativeimportqualifiedControl.ArrowasArrowimportControl.MonadimportControl.Monad.STimportData.BitsimportData.BoolimportqualifiedData.CharasCharimportData.CompleximportqualifiedData.FoldableasFoldableimportData.FunctionimportqualifiedData.ListasListimportData.MaybeimportData.MonoidimportData.OrdimportData.RatioimportData.SemigroupimportqualifiedData.WordasWordimportForeignhidingvoidimportGHC.ExtsimportUnsafe.Coerce{- array -}importqualifiedData.Array.IOasArrIOimportqualifiedData.Array.MArrayasArrMAimportqualifiedData.Array.STasArrSTimportqualifiedData.Array.StorableasArrStoreimportqualifiedData.Array.UnboxedasArrU{- bytestring -}importqualifiedData.ByteStringasBSimportqualifiedData.ByteString.BuilderasBSBimportqualifiedData.ByteString.Builder.ExtraasBSBEimportqualifiedData.ByteString.CharasBSCimportqualifiedData.ByteString.LazyasBSLimportqualifiedData.ByteString.Lazy.BuilderasBSLBimportqualifiedData.ByteString.Lazy.CharasBSLCimportqualifiedData.ByteString.UnsafeasBSU{- containers -}importqualifiedData.GraphasGraphimportData.IntMapIntMapimportqualifiedData.IntMapasIntMapimportData.IntSetIntSetimportqualifiedData.IntSetasIntSetimportqualifiedData.SequenceasSeqimportqualifiedData.TreeasTree{- integer-gmp -}importGHC.Integer.GMP.Internals{- time -}importqualifiedData.Time.CalendarasCalenderimportqualifiedData.Time.Calendar.EasterasCalenderEimportqualifiedData.Time.Calendar.JulianasCalenderJimportqualifiedData.Time.Calendar.MonthDayasCalenderMimportqualifiedData.Time.Calendar.OrdinalDateasCalenderDimportqualifiedData.Time.Calendar.WeekDateasCalenderWimportqualifiedData.Time.LocalTimeasLocalTime{- transformers -}importqualifiedControl.Monad.Trans.AccumasTAccumimportqualifiedControl.Monad.Trans.ContasTContimportqualifiedControl.Monad.Trans.IdentityasTIdimportqualifiedControl.Monad.Trans.ReaderasTReaderimportqualifiedControl.Monad.Trans.State.LazyasTStateLimportqualifiedControl.Monad.Trans.State.StrictasTStateSimportqualifiedControl.Monad.Trans.Writer.CPSasTWriteCimportqualifiedControl.Monad.Trans.Writer.LazyasTWriteLimportqualifiedControl.Monad.Trans.Writer.StrictasTWriteS{- vector -}importqualifiedData.VectorasVimportqualifiedData.Vector.GenericasVGimportqualifiedData.Vector.Generic.MutableasVGMimportqualifiedData.Vector.MutableasVMimportqualifiedData.Vector.PrimitiveasVPimportqualifiedData.Vector.Primitive.MutableasVPMimportqualifiedData.Vector.UnboxedasVUimportqualifiedData.Vector.Unboxed.MutableasVUM---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------main::IO()main = dom <- parse1a <- parseM mlet b = VU.generate m (\i -> nCk (m-1) i)print . VU.sum $ VU.zipWith (*) (VU.map intMod a) b-------------------------------------------------------------------------------fi::Int->Integerfi = fromIntegralfI::Integer->IntfI = fromIntegergcdInt::Int->Int->IntgcdInt a b = fI $ gcdInteger (fi a) (fi b)gcdextInt::Int->Int->IntIntgcdextInt a b = case gcdExtInteger c d of(# x, y #) -> (fI x, fI y)wherec = fromIntegral ad = fromIntegral blcmInt::Int->Int->IntlcmInt a b = fI $ lcmInteger (fi a) (fi b)sqrInt::Int->IntsqrInt = fI . sqrInteger . fipowModInt::Int->Int->Int->IntpowModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo)recipModInt::Int->Int->IntrecipModInt x n = fI $ recipModInteger (fi x) (fi n)-------------------------------------------------------------------------------# MOD 1000000007modulus::Numa=>amodulus = MODINLINEinfixr 8 ^%infixl 7 *%, /%infixl 6 +%, -%(+%)::Int->Int->Int(+%) (I# x#) (I# y#) = case x# +# y# ofr# -> I# (r# -# ((r# >=# MOD#) *# MOD#))INLINE(-%)::Int->Int->Int(-%) (I# x#) (I# y#) = case x# -# y# ofr# -> I# (r# +# ((r# <# 0#) *# MOD#))INLINE(*%) :: Int -> Int -> Int(*%) (I# x#) (I# y#) = I# ((x# *# y#) `remInt#` MOD#)INLINE(/%)::Int->Int->Int(I# x#) /% (I# y#) = go# y# MOD# 1# 0# wherego# a# b# u# v#| isTrue# (b# ># 0#) = case a# `quotInt#` b# ofq# -> 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)wherego !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)INLINEintMod::Integralint=>int->MintintMod x = fromIntegral $ mod (fromIntegral x) MODINLINEintModValidate::Mint->BoolintModValidate (Mint x) = 0 <= x && x < MODINLINEnewtype Mint = Mint { getMint :: Int }deriving newtype (Eq, Ord, Read)instanceShowMintwhereshow (Mint x) = show xinstanceNumMintwhere(+) = coerce (+%)(-) = coerce (-%)(*) = coerce (*%)abs = idsignum = const (Mint 1)fromInteger x = coerce @Int @Mint . fromInteger $ mod x MODinstanceRealMintwheretoRational (Mint x) = toRational xinstanceBoundedMintwhereminBound = Mint 0maxBound = Mint $ MOD - 1instanceEnumMintwheretoEnum = intModfromEnum = coerceinstanceFractionalMintwhere(Mint x) / (Mint y) = Mint (x /% y)fromRational q = fromInteger (numerator q) / fromInteger (denominator q)instanceIntegralMintwherequotRem x y = (x / y, x - x / y * y)toInteger = coerce (toInteger @Int)newtype instanceVUMMVectorsMintMV_MintVUMMVectorsIntnewtype instanceVUVectorMintV_MintVUVectorIntinstanceVUUnboxMintinstanceVGMMVectorVUMMVectorMintwhereINLINEbasicLength (MV_Mint v) = VGM.basicLength vINLINEbasicUnsafeSlice i n (MV_Mint v) = MV_Mint $ VGM.basicUnsafeSlice i n vINLINEbasicOverlaps (MV_Mint v1) (MV_Mint v2) = VGM.basicOverlaps v1 v2INLINEbasicUnsafeNew n = MV_Mint `fmap` VGM.basicUnsafeNew nINLINEbasicInitialize (MV_Mint v) = VGM.basicInitialize vINLINEbasicUnsafeReplicate n x = MV_Mint `fmap` VGM.basicUnsafeReplicate n (coerce x)INLINEbasicUnsafeRead (MV_Mint v) i = coerce `fmap` VGM.basicUnsafeRead v iINLINEbasicUnsafeWrite (MV_Mint v) i x = VGM.basicUnsafeWrite v i (coerce x)INLINEbasicClear (MV_Mint v) = VGM.basicClear vINLINEbasicSet (MV_Mint v) x = VGM.basicSet v (coerce x)INLINEbasicUnsafeCopy (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeCopy v1 v2INLINEbasicUnsafeMove (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeMove v1 v2INLINEbasicUnsafeGrow (MV_Mint v) n = MV_Mint `fmap` VGM.basicUnsafeGrow v ninstanceVGVectorVUVectorMintwhereINLINEbasicUnsafeFreeze (MV_Mint v) = V_Mint `fmap` VG.basicUnsafeFreeze vINLINEbasicUnsafeThaw (V_Mint v) = MV_Mint `fmap` VG.basicUnsafeThaw vINLINEbasicLength (V_Mint v) = VG.basicLength vINLINEbasicUnsafeSlice i n (V_Mint v) = V_Mint $ VG.basicUnsafeSlice i n vINLINEbasicUnsafeIndexM (V_Mint v) i = coerce `fmap` VG.basicUnsafeIndexM v ibasicUnsafeCopy (MV_Mint mv) (V_Mint v) = VG.basicUnsafeCopy mv vINLINEelemseq _ = seqfact::Int->Mintfact = VU.unsafeIndex factCacheINLINErecipFact::Int->MintrecipFact = VU.unsafeIndex recipFactCacheINLINEinvFact::Int->MintinvFact x = recipFact x * fact (x - 1)INLINEnPk::Int->Int->MintnPk n k| n < k = 0| otherwise = fact n * recipFact kINLINEnCk::Int->Int->MintnCk n k| n < k = Mint 0| otherwise = fact n * recipFact (n - k) * recipFact kINLINEnHk::Int->Int->MintnHk n k| n < 0 || k < 0 = Mint 0| k == 0 = Mint 1| otherwise = nCk (n + k - 1) kINLINE# FACT_CACHE_SIZE 200000factCacheSize::IntfactCacheSize = min (modulus - 1) FACT_CACHE_SIZEINLINEfactCache::VUVectorMintfactCache = VU.scanl' (\ x y -> x * coerce y) (1 :: Mint) $ VU.generate factCacheSize (+ 1)recipFactCache::VUVectorMintrecipFactCache = VU.scanr' ((*) . coerce) (1 / factCache VU.! factCacheSize) $ VU.generate factCacheSize (+ 1)powN::Int->VUVectorMintpowN n = VU.scanl' (\acc x -> acc * intMod x) 1 $ VU.replicate factCacheSize nstirling2nd::Int->Int->Mintstirling2nd n k = (snd ret) * (recipFact k)wherexs = zip [0..] $ map f [0..k]f i = (Mint $ powModInt i n modulus) * (nCk k i)ret = List.foldl1' g xsg::IntMint->IntMint->IntMintg acc x| odd (k - fst x) = (fst acc + 1, snd acc - snd x)| otherwise = (fst acc + 1, snd acc + snd x)lagrangePolynomial::Int->VUVectorMint->Int->IOMintlagrangePolynomial k xs t = dodp <- VUM.replicate (k + 1) (Mint 1)pd <- VUM.replicate (k + 1) (Mint 1)forM_ [0 .. k - 1] $ \i -> doa <- VUM.read dp iVUM.write dp (i + 1) (intMod (t - i) * a)forM_ [k, k - 1 .. 1] $ \i -> dob <- VUM.read pd iVUM.write pd (i - 1) (intMod (t - i) * b)ps <- VU.unsafeFreeze dpqs <- VU.unsafeFreeze pdlp xs ps qs (Mint 0) 0 kwherelp::VUVectorMint->VUVectorMint->VUVectorMint->Mint->Int->Int->IOMintlp as ps qs ans i j| i > j = return ans| odd (j - i) = lp as ps qs (ans - tmp) (i + 1) j| otherwise = lp as ps qs (ans + tmp) (i + 1) jwheretmp = (as VU.! i) * (ps VU.! i) * (qs VU.! i) * (recipFact i) * (recipFact (j - i))logMod::Int->Int->Int->MaybeIntlogMod a b p = go 0 bwhere!sp = ceiling . sqrt . fromIntegral $ p!g = powModInt a (-sp) pbabystep x = a * x `rem` pgiantstep x = g * x `rem` ptable::IntMapInt!table = IntMap.fromList $ zip (iterate babystep 1) [0..sp-1]go !i !x| i < sp = case IntMap.lookup x table ofJust j -> Just $! i * sp + jNothing -> go (i + 1) $ giantstep x| otherwise = Nothing-------------------------------------------------------------------------------type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)parseInt::ParserIntparseInt = fmap (Arrow.second BSC8.tail) . BSC8.readIntparseChar::Char->VUVectorCharparseChar = VU.fromListparse1::IOIntparse1 = readLnparse2::IOIntIntparse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLineparse3::IOIntIntIntparse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLineparse4::IOIntIntIntIntparse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLineparseM::Int->IOVUVectorIntparseM m = VU.unfoldrN m parseInt <$> BSC8.getLineparseN::Int->IOVUVectorIntparseN n = VU.replicateM n parse1parseNM::Int->Int->IOVVectorVUVectorIntparseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLineparseANBN::Int->IOVUVectorIntVUVectorIntparseANBN n = dovectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLinereturn $ VU.unzip vectupparseANBNCN::Int->IOVUVectorIntVUVectorIntVUVectorIntparseANBNCN n = dovectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLinereturn $ VU.unzip3 vectup---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------