結果

問題 No.117 組み合わせの数
ユーザー hoghehoghe
提出日時 2020-01-12 06:59:07
言語 Haskell
(9.8.2)
結果
TLE  
実行時間 -
コード長 849 bytes
コンパイル時間 10,736 ms
コンパイル使用メモリ 173,312 KB
実行使用メモリ 14,752 KB
最終ジャッジ日時 2024-05-05 17:51:13
合計ジャッジ時間 23,022 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 = foldl1 (\x y -> x * y `mod` q) [1..n]

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