結果
問題 | No.117 組み合わせの数 |
ユーザー | なお |
提出日時 | 2015-01-04 23:56:08 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,208 bytes |
コンパイル時間 | 1,313 ms |
コンパイル使用メモリ | 160,496 KB |
実行使用メモリ | 19,092 KB |
最終ジャッジ日時 | 2024-06-13 02:26:59 |
合計ジャッジ時間 | 2,231 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) int T; ll fact[2000001]; const int MOD = 1000000000+7; void init(){ fact[0] = fact[1] = 1; for(int i = 2; i <= 2000000; i++){ fact[i] = (fact[i-1] * i) % MOD; } } ll extgcd(ll a,ll b,ll &m,ll &n){ll g=a;m=1;n=0;if(b)g=extgcd(b,a%b,n,m),n-=(a/b)*m;return g;} ll divmod(ll n, ll m, ll mod){ ll a,b; extgcd(m,mod,a,b); return (n * a) % mod; } int c(int n, int r){ if(n < r) return 0; return divmod(fact[n], (fact[r] * fact[n-r])%MOD, MOD); } int p(int n, int r){ if(n < r) return 0; return divmod(fact[n], fact[n-r], MOD); } int h(int n, int r){ return c(n+r-1,r); } int main(){ init(); cin >> T; string s; REP(i,T){ int n,m; cin >> s; if(sscanf(s.c_str(), "C(%d,%d)", &n, &m) == 2){ cout << c(n,m) << endl; } if(sscanf(s.c_str(), "P(%d,%d)", &n, &m) == 2){ cout << p(n,m) << endl; } if(sscanf(s.c_str(), "H(%d,%d)", &n, &m) == 2){ cout << h(n,m) << endl; } } }