結果

問題 No.109 N! mod M
コンテスト
ユーザー かりあげクン
提出日時 2020-09-26 17:45:27
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,104 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 157,184 KB
最終ジャッジ日時 2024-11-14 23:50:40
合計ジャッジ時間 755 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

{-# 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) * powModInt (foldl1' (\acc x -> flip mod m $ acc * (mod x m)) [n + 1 .. m - 1]) (m - 2) 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)]
0