結果

問題 No.117 組み合わせの数
ユーザー hoghehoghe
提出日時 2020-01-12 08:51:21
言語 Haskell
(9.8.2)
結果
TLE  
実行時間 -
コード長 869 bytes
コンパイル時間 8,713 ms
コンパイル使用メモリ 172,032 KB
実行使用メモリ 181,120 KB
最終ジャッジ日時 2024-05-05 21:12:08
合計ジャッジ時間 20,375 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import Control.Monad (replicateM_)

q = 10^9 + 7 :: Int

fac 0 = 1
fac n = memo !! (n-1)
memo = scanl1 (\x y -> x * y `mod` q) [1..]

modInv a =
    let (x, _) = extGCD a q
    in  x `mod` q
    where
    extGCD a 0 = (1, 0)
    extGCD a b =
        let (x, y) = extGCD b $ a `mod` b
        in  (y, x - (a `div` b) * y)

c n k
    | n < k     = 0
    | otherwise = fac n * modInv (fac k * fac (n - k)) `mod` q
p n k
    | n < k     = 0
    | otherwise = fac n * modInv (fac (n - k)) `mod` q
h 1 k = 1
h n k = fac (n + k - 1) * modInv (fac k * fac (n - 1)) `mod` q

f x = do
    let (a:ns)  = init $ map g x
        (n:k:_) = map read $ words ns
    case a of
        'C' -> c n k
        'P' -> p n k
        'H' -> h n k
    where
        g '(' = ' '
        g ',' = ' '
        g x   = x

main = do
    t <- read <$> getLine
    replicateM_ t $ print . f =<< getLine
0