{-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE RecordWildCards #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UnboxedTuples #-} {- base -} import Control.Arrow import Control.Monad import Control.Monad.ST import Data.Bits import Data.Bool import Data.Char import Data.Coerce import Data.Function import Data.Functor.Identity import Data.IORef import Data.Ix import Data.Monoid import Data.Ord import Data.Ratio import Data.Semigroup import Data.STRef import Data.Void import Data.Word import GHC.Exts import Unsafe.Coerce {- array -} import qualified Data.Array as Arr 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.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.Builder.Prim as BSBP import qualified Data.ByteString.Char8 as BSC8 import qualified Data.ByteString.Lazy as BSL import qualified Data.ByteString.Lazy.Char8 as BSLC8 import qualified Data.ByteString.Short as BSS import qualified Data.ByteString.Unsafe as BSU {- integer-gmp -} import qualified GHC.Integer.GMP.Internals as GMP import qualified GHC.Integer.Logarithms.Internals as Log {- vector -} import qualified Data.Vector as V 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.Mutable as VM import qualified Data.Vector.Primitive as VP import qualified Data.Vector.Primitive.Mutable as VPM import qualified Data.Vector.Storable as VS import qualified Data.Vector.Storable.Mutable as VSM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM ------------------------------------------------------------------------------- #define MOD 1000000007 #define Fact_CACHE_SIZE 100100 #define LOG_FACT_CACHE_SIZE 1024 ------------------------------------------------------------------------------- fi :: Int -> Integer fi = fromIntegral {-# INLINE fi #-} fI :: Integer -> Int fI = fromInteger {-# INLINE fI #-} floorSqrt :: Int -> Int floorSqrt = floor . sqrt . fromIntegral {-# INLINE floorSqrt #-} floorLog2 :: Int -> Int floorLog2 x = fromIntegral $ unsafeShiftR y 52 - 1023 where y :: Word64 y = unsafeCoerce (fromIntegral x :: Double) {-# INLINE floorLog2 #-} powModInt :: Int -> Int -> Int -> Int powModInt a b c = fI $ GMP.powModInteger (fi a) (fi b) (fi c) {-# INLINE powModInt #-} recipModInt :: Int -> Int -> Int recipModInt a m = fI $ GMP.recipModInteger (fi a) (fi m) {-# INLINE recipModInt #-} gcdext :: Int -> Int -> (Int, Int, Int) -- a * x + b * y = d => (x, y, d) (d = gcd a b) gcdext a b = (x, y, d) where d = gcd a b (x, y) = case GMP.gcdExtInteger (fi a) (fi b) of (# p, q #) -> (fI p, fI q) {-# INLINE gcdext #-} modInv :: Int -> Int -> Int modInv a mo | 1 == g = mkPos i | otherwise = -1 where (i, _, g) = gcdext a mo mkPos x | x < 0 = x + mo | otherwise = x {-# INLINE modInv #-} stream :: Monad m => Int -> Int -> VFSM.Stream m Int stream !l !r = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + 1) | otherwise = return $ VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] stream #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (stream 0 n) {-# INLINE rep #-} streamR :: (Monad m) => Int -> Int -> VFSM.Stream m Int streamR !l !r = VFSM.Stream step (r - 1) where step x | x >= l = return $ VFSM.Yield x (x - 1) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamR #-} rev :: (Monad m) => Int -> (Int -> m ()) -> m () rev !n = flip VFSM.mapM_ (streamR 0 n) {-# INLINE rev #-} streamStep :: (Monad m) => Int -> Int -> Int -> VFSM.Stream m Int streamStep !l !r !d = VFSM.Stream step l where step x | x < r = return $ VFSM.Yield x (x + d) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamStep #-} infixl 8 `shiftRL`, `unsafeShiftRL` shiftRL :: Int -> Int -> Int shiftRL = unsafeShiftRL {-# INLINE shiftRL #-} unsafeShiftRL :: Int -> Int -> Int unsafeShiftRL (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#) {-# INLINE unsafeShiftRL #-} lowerBoundM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int lowerBoundM low high p = go low high where go !low !high | high <= low = return high | otherwise = p mid >>= bool (go (mid + 1) high) (go low mid) where mid = low + unsafeShiftRL (high - low) 1 {-# INLINE lowerBoundM #-} upperBoundM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int upperBoundM low high p = do flg <- p high if flg then return high else subtract 1 <$!> lowerBoundM low high (fmap not.p) {-# INLINE upperBoundM #-} lowerBound :: Int -> Int -> (Int -> Bool) -> Int lowerBound low high p = runIdentity (lowerBoundM low high (return . p)) {-# INLINE lowerBound #-} upperBound :: Int -> Int -> (Int -> Bool) -> Int upperBound low high p = runIdentity (upperBoundM low high (return . p)) {-# INLINE upperBound #-} (.>>.) :: Bits i => i -> Int -> i (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} (.<<.) :: Bits i => i -> Int -> i (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-} (.>>>.) :: Int -> Int -> Int (.>>>.) = unsafeShiftRL {-# INLINE (.>>>.) #-} ------------------------------------------------------------------------------- type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString) parseInt :: Parser Int parseInt = fmap (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 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 isSpace) <$> BSC8.getLine return $ VU.unzip3 vectup ------------------------------------------------------------------------------- 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 #-} instance Num Mint where (+) = coerce (+%) (-) = coerce (-%) (*) = coerce (*%) abs = id signum = const (Mint 1) fromInteger x = coerce @Int @Mint . fromInteger $ mod x modulus 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 Fractional Mint where (/) = coerce (/%) fromRational q = fromInteger (numerator q) / fromInteger (denominator q) newtype instance VU.Vector Mint = V_Mint (VU.Vector Int) newtype instance VUM.MVector s Mint = MV_Mint (VUM.MVector s 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 #-} ------------------------------------------------------------------------------- main :: IO () main = do m <- parse1 as <- parseM m let sumA = VU.sum as let bs = VU.scanl1 (+) as putStrLn $ bool "No" "Yes" $ VU.and $ VU.imap (\i a -> if i == 0 then True else 0 == mod (sumA - bs VU.! (i - 1)) (i + 1)) bs