#569515 (Haskell) No.1220 yukipoker

提出ソース

結果

問題	No.1220 yukipoker
ユーザー	こまる
提出日時	2020-10-22 12:48:22
言語	Haskell (9.8.2)
結果	AC
実行時間	52 ms / 2,000 ms
コード長	13,791 bytes
コンパイル時間	4,330 ms
コンパイル使用メモリ	235,068 KB
実行使用メモリ	14,924 KB
最終ジャッジ日時	2023-09-28 14:35:25
合計ジャッジ時間	4,145 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	7 ms 8,296 KB
testcase_01	AC	7 ms 8,384 KB
testcase_02	AC	7 ms 8,308 KB
testcase_03	AC	7 ms 8,292 KB
testcase_04	AC	7 ms 8,372 KB
testcase_05	AC	7 ms 8,324 KB
testcase_06	AC	7 ms 8,312 KB
testcase_07	AC	7 ms 8,304 KB
testcase_08	AC	7 ms 8,288 KB
testcase_09	AC	7 ms 8,416 KB
testcase_10	AC	6 ms 8,376 KB
testcase_11	AC	32 ms 13,860 KB
testcase_12	AC	32 ms 14,008 KB
testcase_13	AC	42 ms 14,924 KB
testcase_14	AC	43 ms 14,828 KB
testcase_15	AC	33 ms 14,420 KB
testcase_16	AC	42 ms 13,928 KB
testcase_17	AC	33 ms 13,780 KB
testcase_18	AC	32 ms 13,368 KB
testcase_19	AC	52 ms 14,908 KB
testcase_20	AC	52 ms 14,916 KB
testcase_21	AC	8 ms 8,380 KB
testcase_22	AC	7 ms 8,408 KB
testcase_23	AC	7 ms 8,404 KB
testcase_24	AC	7 ms 8,404 KB
testcase_25	AC	7 ms 8,400 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:61:24: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘powModInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerPowMod# instead"
   |
61 | powModInt a b c = fI $ GMP.powModInteger (fi a) (fi b) (fi c)
   |                        ^^^^^^^^^^^^^^^^^

Main.hs:65:24: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘recipModInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerRecipMod# instead"
   |
65 | recipModInt a m = fI $ GMP.recipModInteger (fi a) (fi m)
   |                        ^^^^^^^^^^^^^^^^^^^

Main.hs:72:19: warning: [GHC-68441] [-Wdeprecations]
    In the use of ‘gcdExtInteger’
    (imported from GHC.Integer.GMP.Internals):
    Deprecated: "Use integerGcde instead"
   |
72 |     (x, y) = case GMP.gcdExtInteger (fi a) (fi b) of
   |                   ^^^^^^^^^^^^^^^^^
[2 of 2] Linking a.out

ソースコード

raw source code

{-# 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              #-}

import           Control.Monad
import           Control.Monad.State
import           Data.Bits
import           Data.Bool
import           Data.Char
import           Data.Coerce
import           Data.Functor.Identity
import           Data.Ratio
import           Data.Word
import           GHC.Exts
import           Unsafe.Coerce
import qualified Data.ByteString                   as BS
import qualified Data.ByteString.Char8             as BSC8
import qualified GHC.Integer.GMP.Internals         as GMP
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.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM

-------------------------------------------------------------------------------
#define MOD 1000000007
#define Fact_CACHE_SIZE 100100
#define LOG_FACT_CACHE_SIZE 100100
-------------------------------------------------------------------------------

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 (.>>>.) #-}

-------------------------------------------------------------------------------
-- Input
-------------------------------------------------------------------------------

type CParser a = StateT BSC8.ByteString Maybe a
runCParser :: CParser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString)
runCParser = runStateT
{-# INLINE runCParser #-}
int :: CParser Int
int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace
{-# INLINE int #-}
int1 :: CParser Int
int1 = fmap (subtract 1) int
{-# INLINE int1 #-}
char :: CParser Char
char = coerce BSC8.uncons
{-# INLINE char #-}
byte :: CParser Word8
byte = coerce BS.uncons
{-# INLINE byte #-}
skipSpaces :: CParser ()
skipSpaces = modify' (BSC8.dropWhile isSpace)
{-# INLINE skipSpaces #-}
seqInput :: Int -> IO (VU.Vector Int)
seqInput n = VU.unfoldrN n (runCParser int) <$> BSC8.getLine
{-# INLINE seqInput #-}
parseN2 :: Int -> IO (VU.Vector (Int, Int))
parseN2 n = VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents
{-# INLINE parseN2 #-}
parseN3 :: Int -> IO (VU.Vector (Int, Int, Int))
parseN3 n = VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN3 #-}
parseN4 :: Int -> IO (VU.Vector (Int, Int, Int, Int))
parseN4 n = VU.unfoldrN n (runCParser $ (,,,) <$> int <*> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN4 #-}
parseN5 :: Int -> IO (VU.Vector (Int, Int, Int, Int, Int))
parseN5 n = VU.unfoldrN n (runCParser $ (,,,,) <$> int <*> int <*> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseN5 #-}
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = VU.unzip . VU.unfoldrN n (runCParser $ (,) <$> int <*> int) <$> BSC8.getContents
{-# INLINE parseANBN #-}
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = VU.unzip3 . VU.unfoldrN n (runCParser $ (,,) <$> int <*> int <*> int) <$> BSC8.getContents
{-# INLINE parseANBNCN #-}
type Query5 = (Int, Int, Int, Int, Int)
query5Parser :: CParser Query5
query5Parser = do
  skipSpaces
  t <- char
  case t of
    '0' -> (,,,,) 0 <$> int <*> int <*> int    <*> int
    _   -> (,,,,) 1 <$> int <*> int <*> pure 0 <*> pure 0
parseQ5 :: Int -> IO (VU.Vector Query5)
parseQ5 n = VU.unfoldrN n (runCParser query5Parser) <$> BSC8.getContents
{-# INLINE parseQ5 #-}

-------------------------------------------------------------------------------

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 #-}

-------------------------------------------------------------------------------

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

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

nPk :: Int -> Int -> Mint
nPk n k = fact n * recipFact (n - k)
{-# INLINE nPk #-}

nCk :: Int -> Int -> Mint
nCk n k = fact n * recipFact (n - k) * recipFact k
{-# INLINE nCk #-}

_factCacheSize :: Int
_factCacheSize = Fact_CACHE_SIZE
{-# NOINLINE _factCacheSize #-}

factCacheSize :: Int
factCacheSize = min (modulus - 1) _factCacheSize
{-# 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 #-}

-------------------------------------------------------------------------------

logFactCacheSize :: Int
logFactCacheSize = LOG_FACT_CACHE_SIZE
{-# NOINLINE logFactCacheSize #-}

logFactCache :: VU.Vector Double
logFactCache = VU.scanl' (+) 0.0 $ VU.generate logFactCacheSize (log . fromIntegral . (+1))
{-# NOINLINE logFactCache #-}

logFact :: Int -> Double
logFact = VU.unsafeIndex logFactCache
{-# INLINE logFact #-}

lognPk :: Int -> Int -> Double
lognPk n k = logFact n - logFact (n - k)
{-# INLINE lognPk #-}

lognCk :: Int -> Int -> Double
lognCk n k = logFact n - logFact k - logFact (n - k)
{-# INLINE lognCk #-}

-------------------------------------------------------------------------------

main :: IO ()
main = do
  query <- readLn :: IO Int
  qs    <- parseN3 query
  putStr . unlines . map (bool "Straight" "Flush") . VU.toList $ solver qs

solver :: VU.Vector (Int, Int, Int) -> VU.Vector Bool
solver = VU.map (\(n, m, k) -> (log (fromIntegral m) + lognCk n k) < ((log (fromIntegral (n - k + 1))) + ((fromIntegral k) * log (fromIntegral m))))

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード