結果
問題 | No.117 組み合わせの数 |
ユーザー | face4 |
提出日時 | 2018-10-09 17:11:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 226 ms / 5,000 ms |
コード長 | 1,330 bytes |
コンパイル時間 | 666 ms |
コンパイル使用メモリ | 71,040 KB |
実行使用メモリ | 34,560 KB |
最終ジャッジ日時 | 2024-10-12 16:35:38 |
合計ジャッジ時間 | 1,375 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ソースコード
#include<iostream> #include<vector> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll modpow(ll a, ll b, ll p = 1e9+7){ if(b == 0) return 1; if(b % 2 == 0){ ll d = modpow(a, b/2, p); return (d*d) % p; }else{ return (a%p * modpow(a, b-1, p)) % p; } } struct ModComb{ vector<ll> po, inv; ll n; ModComb(ll _n) : n(_n), po(_n), inv(_n) { po[0] = 1; for(int i = 1; i < n; i++) po[i] = (po[i-1] * i) % mod; inv[n-1] = modpow(po[n-1], mod-2, mod); for(int i = n-2; i >= 0; i--) inv[i] = (inv[i+1] * (i+1)) % mod; } ll nCk(ll n, ll k){ if(n < k) return 0; return (((po[n]*inv[n-k])%mod)*inv[k])%mod; } ll nPk(ll n, ll k){ if(n < k) return 0; return (po[n]*inv[n-k])%mod; } ll nHk(ll n, ll k){ if(n == 0 && k == 0) return 1; return nCk(n+k-1, k); } }; int main(){ int t; scanf("%d\n", &t); ModComb mc(2000005); char c; int n, k; for(int i = 0; i < t; i++){ ll ans = 1; scanf("%c(%d,%d)\n", &c, &n, &k); if(c == 'C') cout << mc.nCk(n,k) << endl; if(c == 'P') cout << mc.nPk(n,k) << endl; if(c == 'H') cout << mc.nHk(n,k) << endl; } return 0; }