結果

問題 No.1220 yukipoker
ユーザー こまるこまる
提出日時 2020-10-22 12:48:22
言語 Haskell
(9.8.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 13,791 bytes
コンパイル時間 469 ms
コンパイル使用メモリ 153,728 KB
最終ジャッジ日時 2024-07-21 09:16:03
合計ジャッジ時間 1,404 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:28:1: error: [GHC-87110]
    Could not load module ‘GHC.Integer.GMP.Internals’.
    It is a member of the hidden package ‘integer-gmp-1.1’.
    Use -v to see a list of the files searched for.
   |
28 | import qualified GHC.Integer.GMP.Internals         as GMP
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

{-# 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))))
0