結果

問題 No.117 組み合わせの数
ユーザー hoghehoghe
提出日時 2020-01-12 11:11:17
言語 Haskell
(9.8.2)
結果
TLE  
実行時間 -
コード長 1,128 bytes
コンパイル時間 10,889 ms
コンパイル使用メモリ 187,392 KB
実行使用メモリ 188,580 KB
最終ジャッジ日時 2024-11-28 08:01:13
合計ジャッジ時間 18,155 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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 # 

{-# LANGUAGE Strict            #-}
{-# LANGUAGE OverloadedStrings #-}

import           Control.Monad              (replicateM_)
import           Data.Maybe                 (fromJust)
import qualified Data.ByteString.Char8 as B

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) = B.words $ B.map g x
        (n:k:_) = map fst $ fromJust . sequence $ (map $ B.readInt) 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 <- fmap (fst . fromJust . B.readInt) B.getLine
    replicateM_ t $ print . f =<< B.getLine
0