結果
| 問題 |
No.1126 SUM
|
| ユーザー |
 aoshima
|
| 提出日時 | 2020-07-25 00:03:41 |
| 言語 | Haskell (9.10.1) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,691 bytes |
| コンパイル時間 | 199 ms |
| コンパイル使用メモリ | 160,512 KB |
| 最終ジャッジ日時 | 2024-06-25 23:26:18 |
| 合計ジャッジ時間 | 522 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
Main.hs:24:14: warning: [GHC-53692] [-Wdeprecated-flags]
-XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead
|
24 | {-# LANGUAGE TypeInType #-}
| ^^^^^^^^^^
[1 of 2] Compiling Main ( Main.hs, Main.o )
Main.hs:45:1: error: [GHC-87110]
Could not load module ‘Data.IntMap.Strict’.
It is a member of the hidden package ‘containers-0.6.8’.
Use -v to see a list of the files searched for.
|
45 | import qualified Data.IntMap.Strict as IMap
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Main.hs:46: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 for.
|
46 | import qualified Data.IntSet as ISet
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Main.hs:48:1: error: [GHC-87110]
Could not load module ‘Data.Map.Strict’.
It is a member of the hidden package ‘containers-0.6.8’.
Use -v to see a list of the files searched for.
|
48 | import qualified Data.Map.Strict as Map
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Main.hs:55:1: error: [GHC-87110]
Could not load module ‘Data.Set’.
It is a member of the hidden package ‘containers-0.6.8’.
Use -v to see a list of the files searched for.
|
55 | import qualified Data.Set as Set
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# 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 qualified Control.Arrow as Arrow
import Control.Applicative
import Control.Exception
import Control.Monad
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 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, m) <- getAB
let i = intMod n
let j = intMod m
let xs = VU.generate (m - n + 1) id
print $ VU.sum (VU.map (\k -> comb (k + n) n) xs)
#define MOD 1000000007
#define FACT_CACHE_SIZE 2000000
-------------------------------------------------------------------------------
-- ModInt
-------------------------------------------------------------------------------
{-# 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, VPM.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
{-# INLINE elemseq #-}
elemseq _ = seq
{-# 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
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