結果

問題 No.1191 数え上げを愛したい（数列編）
ユーザー かりあげクンかりあげクン
提出日時 2020-08-29 16:06:21
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 9,314 bytes
コンパイル時間 5,227 ms
コンパイル使用メモリ 156,288 KB
最終ジャッジ日時 2024-11-14 23:44:08
合計ジャッジ時間 5,996 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default

Main.hs:9:28: warning: [GHC-53692] [-Wdeprecated-flags]
    -XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead
  |
9 | {-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}
  |                            ^^^^^^^^^^
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:30: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.
   |
30 | import           Data.IntMap.Strict          (IntMap)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:31: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.
   |
31 | import qualified Data.IntMap.Strict          as IntMap
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:32: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.
   |
32 | import           Data.IntSet                 (IntSet)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:33: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.
   |
33 | import qualified Data.IntSet                 as IntSet
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:34:1: error: [GHC-87110]
    Could not load module ‘Data.Sequence’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
   |
34 | import qualified Data.Sequence               as Seq
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns, BinaryLiterals, CPP, DerivingStrategies  #-}
{-# LANGUAGE DerivingVia, FlexibleContexts, FlexibleInstances       #-}
{-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, LambdaCase #-}
{-# LANGUAGE MagicHash, MultiParamTypeClasses, MultiWayIf           #-}
{-# LANGUAGE NumericUnderscores, OverloadedStrings, PatternSynonyms #-}
{-# LANGUAGE RankNTypes, RecordWildCards, ScopedTypeVariables       #-}
{-# LANGUAGE StandaloneDeriving, TupleSections, TypeApplications    #-}
{-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}

{- base -}
import qualified Control.Arrow               as Arrow
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Bits                   as Bits
import qualified Data.Char                   as Char
import qualified Data.Foldable               as Foldable
import qualified Data.List                   as List
import           Data.Monoid
import           Data.Ord
import           Data.Ratio
import           Data.Semigroup
import qualified Data.Word                   as Word
import           GHC.Exts
import           Foreign                     hiding (void)
import           Unsafe.Coerce
{- bytestring -}
import qualified Data.ByteString.Char8       as BSC8
{- containers -}
import           Data.IntMap.Strict          (IntMap)
import qualified Data.IntMap.Strict          as IntMap
import           Data.IntSet                 (IntSet)
import qualified Data.IntSet                 as IntSet
import qualified Data.Sequence               as Seq
{- mtl -}
import           Control.Monad.State.Strict
{- transformers -}
import           Control.Monad.Reader
{- 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

#define MOD 998244353

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 Bits..&. 1 == 0 = go acc (y *% y) (Bits.unsafeShiftR m 1)
      | m == 1 = acc *% y
      | otherwise = go (acc *% y) (y *% y) (Bits.unsafeShiftR (m - 1) 1)

newtype Mint = Mint{ getMint :: Int} deriving (Eq, Ord)

-- Mintは数値
instance Num Mint where
  (+) = coerce (+%)
  (-) = coerce (-%)
  (*) = coerce (*%)
  abs                 = id
  signum              = const (Mint 1)
  fromInteger x       = Mint . fromInteger $ mod x modulus
-- Mintは表示可能
instance Show Mint where
  show (Mint x) = show x
-- Mintは上限・下限を持つ
instance Bounded Mint where
  minBound = Mint 0
  maxBound = Mint $ MOD - 1
-- Mintは列挙型
instance Enum Mint where
  toEnum = intMod
  fromEnum = fromIntegral
-- Mintは実数
instance Real Mint where
  toRational (Mint x) = toRational x
-- Mintは有理数
instance Fractional Mint where
  (Mint x) / (Mint y) = Mint (x /% y)
  fromRational q      = fromInteger (numerator q) / fromInteger (denominator q)
-- Mintは整数
instance Integral Mint where
  quotRem x y = (x / y, x - x / y * y)
  toInteger (Mint x) = toInteger x


newtype instance VUM.MVector s Mint = MV_Mint (VUM.MVector s Int)
newtype instance VU.Vector Mint     =  V_Mint (VU.Vector Int)

-- MintをVectorに乗せることができる
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


intMod :: (Integral int) => int -> Mint
intMod x = fromIntegral $ mod (fromIntegral x) MOD
{-# INLINE intMod #-}
mintValidate :: Mint -> Bool
mintValidate (Mint x) = 0 <= x && x < MOD
{-# INLINE mintValidate #-}

-- utils
{-# INLINE fact #-}
fact :: Int -> Mint
fact = VU.unsafeIndex factCache

{-# INLINE recipFact #-}
recipFact :: Int -> Mint
recipFact = VU.unsafeIndex recipFactCache

{-# INLINE perm #-}
perm :: Int -> Int -> Mint
perm n k
  | n < k     = 0
  | otherwise = fact n * recipFact k

{-# INLINE comb #-}
comb :: Int -> Int -> Mint
comb n k
  | n < k     = Mint 0
  | otherwise = fact n * recipFact (n - k) * recipFact k

#define FACT_CACHE_SIZE 2000000

{-# INLINE factCacheSize #-}
factCacheSize :: Int
factCacheSize = min (modulus - 1) FACT_CACHE_SIZE

{-# NOINLINE factCache #-}
factCache :: VU.Vector Mint
factCache = VU.scanl' (\ x y -> x * coerce y) (1 :: Mint) $ VU.generate factCacheSize (+ 1)
{-# NOINLINE recipFactCache #-}
recipFactCache :: VU.Vector Mint
recipFactCache = VU.scanr' ((*) . coerce) (1 / factCache VU.! factCacheSize) $ VU.generate factCacheSize (+ 1)

powN :: Int -> VU.Vector Mint
powN n = VU.scanl' (\acc x -> acc * intMod x) 1 $ VU.replicate factCacheSize n

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
pint :: StateT BSC8.ByteString Maybe Int
pint = coerce $ BSC8.readInt . BSC8.dropWhile Char.isSpace
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 = VU.unzip . VU.unfoldrN n (runStateT $ (,) <$> pint <*> pint) <$> BSC8.getContents
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = VU.unzip3 . VU.unfoldrN n (runStateT $ (,,) <$> pint <*> pint <*> pint) <$> BSC8.getContents


main :: IO ()
main = do
  (n, m, a, b) <- parse4
  if 1 + a * (n - 1) > m || a * (n - 1) > b
    then print 0
    else print $ solver n m a b

solver :: Int -> Int -> Int -> Int -> Int
solver n m a b = coerce $ ans * (fact n)
  where
    ans = loop 1 0
      where
        loop s ret
          | s == (m + 1)        = ret
          | s + a * (n - 1) > m = ret
          | otherwise = loop (s + 1) ret'
          where
            ret' = ret + comb ((min m (s + b)) - s - (a - 1) * (n - 1)) (n - 1)
0