結果
| 問題 | No.109 N! mod M |
| ユーザー |
 かりあげクン
|
| 提出日時 | 2020-09-26 21:49:33 |
| 言語 | Haskell (9.8.2) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,098 bytes |
| コンパイル時間 | 133 ms |
| コンパイル使用メモリ | 154,112 KB |
| 最終ジャッジ日時 | 2024-04-27 03:30:21 |
| 合計ジャッジ時間 | 454 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、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:15: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.
|
15 | import qualified GHC.Integer.GMP.Internals as GMP
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}
{- base -}
import Control.Arrow
import Data.Bits
import Data.Char
import Data.List (foldl1')
import Data.Word
import GHC.Exts
import Unsafe.Coerce
{- bytestring -}
import qualified Data.ByteString.Char8 as BSC8
{- integer-gmp -}
import qualified GHC.Integer.GMP.Internals as GMP
{- vector -}
import qualified Data.Vector as V
import qualified Data.Vector.Fusion.Stream.Monadic as VFSM
import qualified Data.Vector.Unboxed as VU
main :: IO ()
main = do
query <- parse1
rep query $ \_ -> do
print . solver =<< parse2
solver :: (Int, Int) -> Int
solver (n, m)
| m == 1 = 0
| n >= m = 0
| n <= 1 = 1
| m <= 200000 = flip mod m $ foldl1' (\acc x -> mod (acc * (mod x m)) m) [1..n]
| isPrime m = if n + 1 < m - 1
then flip mod m $ (m - 1) * recipModInt (foldl1' (\acc x -> flip mod m $ acc * (mod x m)) [n + 1 .. m - 1]) m
else if n == m - 1 then n else 1
| otherwise = if n >= (m .>>. 1)
then 0
else flip mod m $ foldl1' (\acc x -> mod (acc * (mod x m)) m) [1..n]
-------------------------------------------------------------------------------
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
-------------------------------------------------------------------------------
infixl 8 .>>., .<<., .>>>.
infixl 6 .^.
(.^.) :: Bits i => i -> i -> i
(.^.) = xor
(.>>.) :: Bits i => i -> Int -> i
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}
(.<<.) :: Bits i => i -> Int -> i
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}
(.>>>.) :: Int -> Int -> Int
(.>>>.) (I# x#) (I# i#) = I# (uncheckedIShiftRL# x# i#)
{-# INLINE (.>>>.) #-}
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 #-}
bitReverse :: Int -> Int
bitReverse
= unsafeCoerce
. step 32 0xffffffff00000000 0x00000000ffffffff
. step 16 0xffff0000ffff0000 0x0000ffff0000ffff
. step 08 0xff00ff00ff00ff00 0x00ff00ff00ff00ff
. step 04 0xf0f0f0f0f0f0f0f0 0x0f0f0f0f0f0f0f0f
. step 02 0xcccccccccccccccc 0x3333333333333333
. step 01 0xaaaaaaaaaaaaaaaa 0x5555555555555555
. unsafeCoerce
where
step :: Int -> Word64 -> Word64 -> Word64 -> Word64
step i ml mr = \ !x -> (x .&. ml) .>>. i .|. (x .&. mr) .<<. i
{-# INLINE step #-}
-------------------------------------------------------------------------------
isPrime :: Int -> Bool
isPrime k
| k <= 3 = k == 2 || k == 3
| even k = False
| otherwise = millerRabin k
where
millerRabin :: Int -> Bool
millerRabin n
| n < 2047 = loop [2]
| n < 1373653 = loop [2,3]
| n < 9080191 = loop [31,73]
| n < 25326001 = loop [2,3,5]
| n < 4759123141 = loop [2,7,61]
| n < 1122004669633 = loop [2,13,23,1662803]
| n < 2152302898747 = loop [2,3,5,7,11]
| n < 3474749660383 = loop [2,3,5,7,11,13]
| n < 341550071728321 = loop [2,3,5,7,11,13,17]
| otherwise = loop [2,325,9375,28178,450775,9780504,1795265022]
where
!m = n - 1
!s = countTrailingZeros m
!d = m .>>. s
check1 :: Int -> Bool
check1 !a = powModInt a d n /= 1
{-# INLINE check1 #-}
check2 :: Int -> Int -> Bool
check2 !a !i = (powModInt a (d * (1 .<<. i)) n) /= m
{-# INLINE check2 #-}
loop [] = True
loop (a:as)
| check1 a && allok = False
| otherwise = loop as
where
allok = all (check2 a) [0..(s - 1)]