#549233 (Haskell) No.1081 和の和

• 問題: 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

コンパイルメッセージ

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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE BinaryLiterals             #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DeriveFunctor              #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE DerivingVia                #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE FlexibleInstances          #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE KindSignatures             #-}
{-# LANGUAGE LambdaCase                 #-}
{-# LANGUAGE MagicHash                  #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE MultiWayIf                 #-}
{-# LANGUAGE NumericUnderscores         #-}
{-# LANGUAGE OverloadedStrings          #-}
{-# LANGUAGE PatternSynonyms            #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE RecordWildCards            #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE StandaloneDeriving         #-}
{-# LANGUAGE TupleSections              #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE TypeInType                 #-}
{-# LANGUAGE UnboxedTuples              #-}
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
{- base -}
import           Control.Applicative
import qualified Control.Arrow                     as Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import qualified Data.Char                         as Char
import           Data.Complex
import qualified Data.Foldable                     as Foldable
import           Data.Function
import qualified Data.List                         as List
import           Data.Maybe
import           Data.Monoid
import           Data.Ord
import           Data.Ratio
import           Data.Semigroup
import qualified Data.Word                         as Word
import           Foreign                           hiding (void)
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array.IO                     as ArrIO
import qualified Data.Array.MArray                 as ArrMA
import qualified Data.Array.ST                     as ArrST
import qualified Data.Array.Storable               as ArrStore
import qualified Data.Array.Unboxed                as ArrU
{- bytestring -}
import qualified Data.ByteString                   as BS
import qualified Data.ByteString.Builder           as BSB
import qualified Data.ByteString.Builder.Extra     as BSBE
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.ByteString.Lazy              as BSL
import qualified Data.ByteString.Lazy.Builder      as BSLB
import qualified Data.ByteString.Lazy.Char8        as BSLC8
import qualified Data.ByteString.Unsafe            as BSU
{- containers -}
import qualified Data.Graph                        as Graph
import           Data.IntMap                       (IntMap)
import qualified Data.IntMap                       as IntMap
import           Data.IntSet                       (IntSet)
import qualified Data.IntSet                       as IntSet
import qualified Data.Sequence                     as Seq
import qualified Data.Tree                         as Tree
{- integer-gmp -}
import           GHC.Integer.GMP.Internals
{- time -}
import qualified Data.Time.Calendar                as Calender
import qualified Data.Time.Calendar.Easter         as CalenderE
import qualified Data.Time.Calendar.Julian         as CalenderJ
import qualified Data.Time.Calendar.MonthDay       as CalenderM
import qualified Data.Time.Calendar.OrdinalDate    as CalenderD
import qualified Data.Time.Calendar.WeekDate       as CalenderW
import qualified Data.Time.LocalTime               as LocalTime
{- transformers -}
import qualified Control.Monad.Trans.Accum         as TAccum
import qualified Control.Monad.Trans.Cont          as TCont
import qualified Control.Monad.Trans.Identity      as TId
import qualified Control.Monad.Trans.Reader        as TReader
import qualified Control.Monad.Trans.State.Lazy    as TStateL
import qualified Control.Monad.Trans.State.Strict  as TStateS
import qualified Control.Monad.Trans.Writer.CPS    as TWriteC
import qualified Control.Monad.Trans.Writer.Lazy   as TWriteL
import qualified Control.Monad.Trans.Writer.Strict as TWriteS
{- vector -}
import qualified Data.Vector                       as V
import qualified Data.Vector.Generic               as VG
import qualified Data.Vector.Generic.Mutable       as VGM
import qualified Data.Vector.Mutable               as VM
import qualified Data.Vector.Primitive             as VP
import qualified Data.Vector.Primitive.Mutable     as VPM
import qualified Data.Vector.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
main :: IO ()
main = do
  m <- parse1
  a <- parseM m
  let b = VU.generate m (\i -> nCk (m-1) i) 
  print . VU.sum $ VU.zipWith (*) (VU.map intMod a) b
-------------------------------------------------------------------------------
fi :: Int -> Integer
fi = fromIntegral
fI :: Integer -> Int
fI = fromInteger
gcdInt :: Int -> Int -> Int
gcdInt a b = fI $ gcdInteger (fi a) (fi b)
gcdextInt :: Int -> Int -> (Int, Int)
gcdextInt a b = case gcdExtInteger c d of
  (# x, y #) -> (fI x, fI y)
  where
    c = fromIntegral a
    d = fromIntegral b
lcmInt :: Int -> Int -> Int
lcmInt a b = fI $ lcmInteger (fi a) (fi b)
sqrInt :: Int -> Int
sqrInt = fI . sqrInteger . fi
powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo)
recipModInt :: Int -> Int -> Int
recipModInt x n = fI $ recipModInteger (fi x) (fi n)
-------------------------------------------------------------------------------
#define MOD 1000000007
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#) = I# ((x# *# y#) `remInt#` MOD#)
{-# 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)
{-# INLINE (^%) #-}
intMod :: (Integral int) => int -> Mint
intMod x = fromIntegral $ mod (fromIntegral x) MOD
{-# INLINE intMod #-}
intModValidate :: Mint -> Bool
intModValidate (Mint x) = 0 <= x && x < MOD
{-# INLINE intModValidate #-}
newtype Mint = Mint { getMint :: Int }
  deriving newtype (Eq, Ord, Read)
instance Show Mint where
  show (Mint x) = show x
instance Num Mint where
  (+) = coerce (+%)
  (-) = coerce (-%)
  (*) = coerce (*%)
  abs = id
  signum = const (Mint 1)
  fromInteger x = coerce @Int @Mint . fromInteger $ mod x MOD
instance Real Mint where
  toRational (Mint x) = toRational x
instance Bounded Mint where
  minBound = Mint 0
  maxBound = Mint $ MOD - 1
instance Enum Mint where
  toEnum = intMod
  fromEnum = coerce
instance Fractional Mint where
  (Mint x) / (Mint y) = Mint (x /% y)
  fromRational q      = fromInteger (numerator q) / fromInteger (denominator q)
instance Integral Mint where
  quotRem x y = (x / y, x - x / y * y)
  toInteger = coerce (toInteger @Int)
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
  {-# INLINE basicLength #-}
  basicLength (MV_Mint v) = VGM.basicLength v
  {-# INLINE basicUnsafeSlice #-}
  basicUnsafeSlice i n (MV_Mint v) = MV_Mint $ VGM.basicUnsafeSlice i n v
  {-# INLINE basicOverlaps #-}
  basicOverlaps (MV_Mint v1) (MV_Mint v2) = VGM.basicOverlaps v1 v2
  {-# INLINE basicUnsafeNew #-}
  basicUnsafeNew n = MV_Mint `fmap` VGM.basicUnsafeNew n
  {-# INLINE basicInitialize #-}
  basicInitialize (MV_Mint v) = VGM.basicInitialize v
  {-# INLINE basicUnsafeReplicate #-}
  basicUnsafeReplicate n x = MV_Mint `fmap` VGM.basicUnsafeReplicate n (coerce x)
  {-# INLINE basicUnsafeRead #-}
  basicUnsafeRead (MV_Mint v) i = coerce `fmap` VGM.basicUnsafeRead v i
  {-# INLINE basicUnsafeWrite #-}
  basicUnsafeWrite (MV_Mint v) i x = VGM.basicUnsafeWrite v i (coerce x)
  {-# INLINE basicClear #-}
  basicClear (MV_Mint v) = VGM.basicClear v
  {-# INLINE basicSet #-}
  basicSet (MV_Mint v) x = VGM.basicSet v (coerce x)
  {-# INLINE basicUnsafeCopy #-}
  basicUnsafeCopy (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeCopy v1 v2
  {-# INLINE basicUnsafeMove #-}
  basicUnsafeMove (MV_Mint v1) (MV_Mint v2) = VGM.basicUnsafeMove v1 v2
  {-# INLINE basicUnsafeGrow #-}
  basicUnsafeGrow (MV_Mint v) n = MV_Mint `fmap` VGM.basicUnsafeGrow v n
instance VG.Vector VU.Vector Mint where
  {-# INLINE basicUnsafeFreeze #-}
  basicUnsafeFreeze (MV_Mint v) = V_Mint `fmap` VG.basicUnsafeFreeze v
  {-# INLINE basicUnsafeThaw #-}
  basicUnsafeThaw (V_Mint v) = MV_Mint `fmap` VG.basicUnsafeThaw v
  {-# INLINE basicLength #-}
  basicLength (V_Mint v) = VG.basicLength v
  {-# INLINE basicUnsafeSlice #-}
  basicUnsafeSlice i n (V_Mint v) = V_Mint $ VG.basicUnsafeSlice i n v
  {-# INLINE basicUnsafeIndexM #-}
  basicUnsafeIndexM (V_Mint v) i = coerce `fmap` VG.basicUnsafeIndexM v i
  basicUnsafeCopy (MV_Mint mv) (V_Mint v) = VG.basicUnsafeCopy mv v
  {-# INLINE elemseq #-}
  elemseq _ = seq
fact :: Int -> Mint
fact = VU.unsafeIndex factCache
{-# INLINE fact #-}
recipFact :: Int -> Mint
recipFact = VU.unsafeIndex recipFactCache
{-# INLINE recipFact #-}
invFact :: Int -> Mint
invFact x = recipFact x * fact (x - 1)
{-# INLINE invFact #-}
nPk :: Int -> Int -> Mint
nPk n k
  | n < k     = 0
  | otherwise = fact n * recipFact k
{-# INLINE nPk #-}
nCk :: Int -> Int -> Mint
nCk n k
  | n < k     = Mint 0
  | otherwise = fact n * recipFact (n - k) * recipFact k
{-# INLINE nCk #-}
nHk :: Int -> Int -> Mint
nHk n k
  | n < 0 || k < 0 = Mint 0
  | k == 0         = Mint 1
  | otherwise      = nCk (n + k - 1) k
{-# INLINE nHk #-}
#define FACT_CACHE_SIZE 200000
factCacheSize :: Int
factCacheSize = min (modulus - 1) FACT_CACHE_SIZE
{-# INLINE factCacheSize #-}
factCache :: VU.Vector Mint
factCache = VU.scanl' (\ x y -> x * coerce y) (1 :: Mint) $ VU.generate factCacheSize (+ 1)
{-# NOINLINE factCache #-}
recipFactCache :: VU.Vector Mint
recipFactCache = VU.scanr' ((*) . coerce) (1 / factCache VU.! factCacheSize) $ VU.generate factCacheSize (+ 1)
{-# NOINLINE recipFactCache #-}
powN :: Int -> VU.Vector Mint
powN n = VU.scanl' (\acc x -> acc * intMod x) 1 $ VU.replicate factCacheSize n
stirling2nd :: Int -> Int -> Mint
stirling2nd n k = (snd ret) * (recipFact k)
  where
    xs  = zip [0..] $ map f [0..k]
    f i = (Mint $ powModInt i n modulus) * (nCk k i)
    ret = List.foldl1' g xs
    g :: (Int, Mint) -> (Int, Mint) -> (Int, Mint)
    g acc x
      | odd (k - fst x) = (fst acc + 1, snd acc - snd x)
      | otherwise       = (fst acc + 1, snd acc + snd x)
lagrangePolynomial :: Int -> VU.Vector Mint -> Int -> IO Mint
lagrangePolynomial k xs t = do
  dp <- VUM.replicate (k + 1) (Mint 1)
  pd <- VUM.replicate (k + 1) (Mint 1)
  forM_ [0 .. k - 1] $ \i -> do
    a <- VUM.read dp i
    VUM.write dp (i + 1) (intMod (t - i) * a)
  forM_ [k, k - 1 .. 1] $ \i -> do
    b <- VUM.read pd i
    VUM.write pd (i - 1) (intMod (t - i) * b)
  ps <- VU.unsafeFreeze dp
  qs <- VU.unsafeFreeze pd
  lp xs ps qs (Mint 0) 0 k
    where
      lp :: VU.Vector Mint -> VU.Vector Mint -> VU.Vector Mint -> Mint -> Int -> Int -> IO Mint
      lp 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) j
        where
          tmp = (as VU.! i) * (ps VU.! i) * (qs VU.! i) * (recipFact i) * (recipFact (j - i))
logMod :: Int -> Int -> Int -> Maybe Int
logMod a b p = go 0 b
  where
    !sp = ceiling . sqrt . fromIntegral $ p
    !g  = powModInt a (-sp) p
    babystep x = a * x `rem` p
    giantstep x = g * x `rem` p
    table :: IntMap Int
    !table = IntMap.fromList $ zip (iterate babystep 1) [0..sp-1]
    go !i !x
      | i < sp = case IntMap.lookup x table of
        Just j  -> Just $! i * sp + j
        Nothing -> go (i + 1) $ giantstep x
      | otherwise = Nothing
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8.getLine
  return $ VU.unzip vectup
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile Char.isSpace) <$> BSC8
      .getLine
  return $ VU.unzip3 vectup
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX