結果
問題 | No.117 組み合わせの数 |
ユーザー | 👑 obakyan |
提出日時 | 2019-05-02 23:54:24 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 202 ms / 5,000 ms |
コード長 | 2,097 bytes |
コンパイル時間 | 1,502 ms |
コンパイル使用メモリ | 75,648 KB |
実行使用メモリ | 18,628 KB |
最終ジャッジ日時 | 2023-08-30 04:59:59 |
合計ジャッジ時間 | 1,485 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
ソースコード
#include <cstdio> #include <cstdlib> #include <cstddef> #include <vector> #include <algorithm> #include <cmath> #include <string> #include <iostream> #include <iomanip> #define L64 long long #define MOD (1000000007LL) L64 modpow(L64 src, L64 pow, L64 mod) { L64 res = 1; while (0 < pow) { if (pow % 2 == 1) { res = (res * src) % mod; pow--; } src = (src * src) % mod; pow /= 2; } return res; } L64 modinv(L64 src, L64 mod) { return modpow(src, mod - 2, mod); } int main(void) { std::vector<L64> factorials; factorials.resize(2000001); factorials[0] = 1; char c[100]; L64 a, b; int t; char tp; for(L64 i = 1; i <= 2000000; i++){ factorials[i] = (factorials[i - 1] * i) % MOD; } std::cin >> t; for(int i = 0; i < t; i++){ scanf("%s", &c); tp = c[0]; int pos = 2; a = 0; while(true){ char tmp = c[pos]; if(tmp == ','){ pos++; break; } else { a = a * 10LL + (L64)(tmp - 48); pos++; } } b = 0; while(true){ char tmp = c[pos]; if(tmp == ')'){ pos++; break; } else { b = b * 10LL + (L64)(tmp - 48); pos++; } } if(a == 0){ if(b == 0){ std::cout << 1 << std::endl; } else { std::cout << 0 << std::endl; } } else if(tp != 'H' && a < b){ std::cout << 0 << std::endl; } else if(tp == 'C'){ L64 ret = factorials[a]; L64 div = factorials[a - b]; ret = (ret * modinv(div, MOD)) % MOD; div = factorials[b]; ret = (ret * modinv(div, MOD)) % MOD; std::cout << ret << std::endl; } else if(tp == 'P'){ L64 ret = factorials[a]; L64 div = factorials[a - b]; ret = (ret * modinv(div, MOD)) % MOD; std::cout << ret << std::endl; } else { a = a + b - 1; L64 ret = factorials[a]; L64 div = factorials[a - b]; ret = (ret * modinv(div, MOD)) % MOD; div = factorials[b]; ret = (ret * modinv(div, MOD)) % MOD; std::cout << ret << std::endl; } } }