結果
| 問題 | No.1081 和の和 |
| ユーザー |
 糸見沙耶香
|
| 提出日時 | 2020-07-20 11:29:11 |
| 言語 | Haskell (9.8.2) |
| 結果 |
AC
|
| 実行時間 | 83 ms / 2,000 ms |
| コード長 | 9,779 bytes |
| コンパイル時間 | 8,987 ms |
| コンパイル使用メモリ | 287,144 KB |
| 実行使用メモリ | 38,460 KB |
| 最終ジャッジ日時 | 2023-08-24 22:43:03 |
| 合計ジャッジ時間 | 11,514 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 83 ms
38,256 KB |
| testcase_01 | AC | 82 ms
38,324 KB |
| testcase_02 | AC | 82 ms
38,272 KB |
| testcase_03 | AC | 83 ms
38,312 KB |
| testcase_04 | AC | 82 ms
38,380 KB |
| testcase_05 | AC | 82 ms
38,328 KB |
| testcase_06 | AC | 83 ms
38,460 KB |
| testcase_07 | AC | 82 ms
38,304 KB |
| testcase_08 | AC | 82 ms
38,460 KB |
| testcase_09 | AC | 82 ms
38,308 KB |
| testcase_10 | AC | 82 ms
38,316 KB |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
Main.hs:24:14: warning: [-Wdeprecated-flags]
-XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead
|
24 | {-# LANGUAGE TypeInType #-}
| ^^^^^^^^^^
[1 of 2] Compiling Main ( Main.hs, Main.o )
[2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE CPP #-}
{-# 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 #-}
import Control.Applicative
import qualified Control.Arrow as Arrow
import Control.Exception
import Control.Monad
-- import qualified Control.Monad.Primitive as Primitive
import Control.Monad.Reader
import Control.Monad.ST
import Control.Monad.State.Strict
import Data.Bifunctor
import Data.Bool
import qualified Data.ByteString as BS
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Char8 as BSC8
import qualified Data.ByteString.Internal as BSI
import qualified Data.ByteString.Unsafe as BSU
import Data.Char
import qualified Data.Foldable as F
import Data.Function
import Data.Functor.Identity
import qualified Data.IntMap.Strict as IMap
import qualified Data.IntSet as ISet
import qualified Data.List as L
import qualified Data.Map.Strict as Map
import qualified Data.Maybe as Maybe
import Data.Monoid
import Data.Ord
-- import qualified Data.Primitive as Prim
import Data.Proxy
import Data.Ratio
import Data.Semigroup
import qualified Data.Set as Set
import Data.Tuple
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
import Debug.Trace
import Foreign hiding (void)
import GHC.Exts
import GHC.TypeLits
import qualified System.IO as IO
import Unsafe.Coerce
main :: IO ()
main = do
n <- readLn :: IO Int
xs <- getAN n
print $ solve n xs
solve :: Int -> VU.Vector Int -> Int
solve n xs = VU.foldl1' (+%) $ VU.map (\i -> (xs VU.! i) *% (coerce $ comb (n - 1) i)) ys
where
ys = VU.generate n id
#define MOD 1000000007
#define FACT_CACHE_SIZE 2000000
{-# INLINE modulus #-}
modulus :: (Num a) => a
modulus = MOD
infixr 8 ^%
infixl 7 *%, /%
infixl 6 +%, -%
{-# INLINE (+%) #-}
(+%) :: 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)
newtype IntMod = IntMod { getIntMod :: Int } deriving newtype (Eq, Ord, Read, Show, Real, VP.Prim)
{-# INLINE intMod #-}
intMod :: (Integral a) => a -> IntMod
intMod x = fromIntegral $ mod (fromIntegral x) MOD
{-# INLINE intModValidate #-}
intModValidate :: IntMod -> Bool
intModValidate (IntMod x) = 0 <= x && x < MOD
instance Bounded IntMod where
minBound = IntMod 0
maxBound = IntMod $ modulus - 1
instance Enum IntMod where
toEnum = intMod
fromEnum = coerce
instance Integral IntMod where
quotRem x y = (x / y, x - x / y * y)
toInteger = coerce (toInteger @Int)
instance Num IntMod where
(+) = coerce (+%)
(-) = coerce (-%)
(*) = coerce (*%)
abs = id
signum = const (IntMod 1)
fromInteger x = coerce @Int @IntMod . fromInteger $ mod x modulus
instance Fractional IntMod where
(/) = coerce (/%)
fromRational q = fromInteger (numerator q) / fromInteger (denominator q)
newtype instance VUM.MVector s IntMod = MV_IntMod (VUM.MVector s Int)
newtype instance VU.Vector IntMod = V_IntMod (VU.Vector Int)
instance VU.Unbox IntMod
instance VGM.MVector VUM.MVector IntMod where
{-# INLINE basicLength #-}
basicLength (MV_IntMod v) = VGM.basicLength v
{-# INLINE basicUnsafeSlice #-}
basicUnsafeSlice i n (MV_IntMod v) = MV_IntMod $ VGM.basicUnsafeSlice i n v
{-# INLINE basicOverlaps #-}
basicOverlaps (MV_IntMod v1) (MV_IntMod v2) = VGM.basicOverlaps v1 v2
{-# INLINE basicUnsafeNew #-}
basicUnsafeNew n = MV_IntMod `fmap` VGM.basicUnsafeNew n
{-# INLINE basicInitialize #-}
basicInitialize (MV_IntMod v) = VGM.basicInitialize v
{-# INLINE basicUnsafeReplicate #-}
basicUnsafeReplicate n x = MV_IntMod `fmap` VGM.basicUnsafeReplicate n (coerce x)
{-# INLINE basicUnsafeRead #-}
basicUnsafeRead (MV_IntMod v) i = coerce `fmap` VGM.basicUnsafeRead v i
{-# INLINE basicUnsafeWrite #-}
basicUnsafeWrite (MV_IntMod v) i x = VGM.basicUnsafeWrite v i (coerce x)
{-# INLINE basicClear #-}
basicClear (MV_IntMod v) = VGM.basicClear v
{-# INLINE basicSet #-}
basicSet (MV_IntMod v) x = VGM.basicSet v (coerce x)
{-# INLINE basicUnsafeCopy #-}
basicUnsafeCopy (MV_IntMod v1) (MV_IntMod v2) = VGM.basicUnsafeCopy v1 v2
{-# INLINE basicUnsafeMove #-}
basicUnsafeMove (MV_IntMod v1) (MV_IntMod v2) = VGM.basicUnsafeMove v1 v2
{-# INLINE basicUnsafeGrow #-}
basicUnsafeGrow (MV_IntMod v) n = MV_IntMod `fmap` VGM.basicUnsafeGrow v n
instance VG.Vector VU.Vector IntMod where
{-# INLINE basicUnsafeFreeze #-}
basicUnsafeFreeze (MV_IntMod v) = V_IntMod `fmap` VG.basicUnsafeFreeze v
{-# INLINE basicUnsafeThaw #-}
basicUnsafeThaw (V_IntMod v) = MV_IntMod `fmap` VG.basicUnsafeThaw v
{-# INLINE basicLength #-}
basicLength (V_IntMod v) = VG.basicLength v
{-# INLINE basicUnsafeSlice #-}
basicUnsafeSlice i n (V_IntMod v) = V_IntMod $ VG.basicUnsafeSlice i n v
{-# INLINE basicUnsafeIndexM #-}
basicUnsafeIndexM (V_IntMod v) i = coerce `fmap` VG.basicUnsafeIndexM v i
basicUnsafeCopy (MV_IntMod mv) (V_IntMod v) = VG.basicUnsafeCopy mv v
elemseq _ = seq; {-# INLINE elemseq #-}
{-# INLINE fact #-}
fact :: Int -> IntMod
fact = VU.unsafeIndex factCache
{-# INLINE recipFact #-}
recipFact :: Int -> IntMod
recipFact = VU.unsafeIndex recipFactCache
{-# INLINE perm #-}
perm :: Int -> Int -> IntMod
perm n k = fact n * recipFact k
{-# INLINE comb #-}
comb :: Int -> Int -> IntMod
comb n k = fact n * recipFact (n - k) * recipFact k
{-# INLINE factCacheSize #-}
factCacheSize :: Int
factCacheSize = min (modulus - 1) FACT_CACHE_SIZE
{-# NOINLINE factCache #-}
factCache :: VU.Vector IntMod
factCache = VU.scanl' (\ x y -> x * coerce y) (1 :: IntMod) $ VU.generate factCacheSize (+ 1)
{-# NOINLINE recipFactCache #-}
recipFactCache :: VU.Vector IntMod
recipFactCache = VU.scanr' ((*) . coerce) (1 / factCache VU.! factCacheSize) $ VU.generate factCacheSize (+ 1)
powN :: Int -> VU.Vector IntMod
powN n = VU.scanl' (\acc x -> acc * intMod x) 1 $ VU.replicate factCacheSize n
getStringList :: IO [String]
getStringList = map BSC8.unpack . BSC8.words <$> BSC8.getLine
-- Intリスト
getInt :: IO [Int]
getInt = L.unfoldr f <$> BSC8.getLine
where
f s = do
(n, s') <- BSC8.readInt s
return (n, BSC8.dropWhile isSpace s')
getIL :: IO [Integer]
getIL = L.unfoldr f <$> BSC8.getLine
where
-- f :: ByteString -> Maybe (Integer, ByteString)
f s = do
(n, s') <- BSC8.readInteger s
return (n, BSC8.dropWhile isSpace s')
getMultiLine :: Int -> IO [[Integer]]
getMultiLine n = replicateM n getIL
readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts :: IO [Int]
readInts = map ( fst . Maybe.fromJust . BSC8.readInt ) . BSC8.words <$> BSC8.getLine
readIntegers :: IO [Integer]
readIntegers = map ( fst . Maybe.fromJust . BSC8.readInteger ) . BSC8.words <$> BSC8.getLine
getI :: BSC8.ByteString -> Maybe (Int, BSC8.ByteString)
getI = fmap (Arrow.second BSC8.tail) . BSC8.readInt
getAB :: IO (Int, Int)
getAB = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 getI <$> BSC8.getLine
getABC :: IO (Int, Int, Int)
getABC = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 getI <$> BSC8.getLine
getAN :: Int -> IO (VU.Vector Int)
getAN n = VU.unfoldrN n getI <$> BSC8.getLine