#557773 (Haskell) No.1220 yukipoker

• 問題: No.1220 yukipoker
• ユーザー: かりあげクン
• 提出日時: 2020-09-25 13:40:32
• 言語: Haskell (9.8.2)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 14,289 bytes
• コンパイル時間: 728 ms
• コンパイル使用メモリ: 167,680 KB
• 最終ジャッジ日時: 2024-11-14 23:50:25
• 合計ジャッジ時間: 2,374 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

コンパイルメッセージ

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:52: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.
   |
52 | import qualified GHC.Integer.GMP.Internals         as GMP
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:53:1: error: [GHC-87110]
    Could not find module ‘GHC.Integer.Logarithms.Internals’.
    Use -v to see a list of the files searched for.
   |
53 | import qualified GHC.Integer.Logarithms.Internals  as Log
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

{-# 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 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 (.>>>.) #-}
-------------------------------------------------------------------------------
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 #-}
-------------------------------------------------------------------------------
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 <- parse1
  rep query $ \_ -> do
    (n, m, k) <- parse3
    putStrLn $ bool "Straight" "Flush" $ (log (fromIntegral m) + lognCk n k) < ((log (fromIntegral (n - k + 1))) + ((fromIntegral k) * log (fromIntegral m)))