結果
問題 | No.117 組み合わせの数 |
ユーザー | hoghe |
提出日時 | 2020-01-12 11:11:17 |
言語 | Haskell (9.8.2) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,128 bytes |
コンパイル時間 | 9,842 ms |
コンパイル使用メモリ | 186,368 KB |
実行使用メモリ | 186,880 KB |
最終ジャッジ日時 | 2024-05-06 04:32:52 |
合計ジャッジ時間 | 21,303 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
コンパイルメッセージ
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
ソースコード
{-# 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