結果
問題 | No.117 組み合わせの数 |
ユーザー |
![]() |
提出日時 | 2016-03-20 02:47:14 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 302 ms / 5,000 ms |
コード長 | 1,791 bytes |
コンパイル時間 | 629 ms |
コンパイル使用メモリ | 86,896 KB |
実行使用メモリ | 26,960 KB |
最終ジャッジ日時 | 2024-10-01 09:21:30 |
合計ジャッジ時間 | 1,629 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
ソースコード
/* -*- coding: utf-8 -*-** 117.cc: No.117 組み合わせの数 - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 1000000;typedef long long ll;const ll MOD = 1000000007;/* typedef *//* global variables */ll fracs[MAX_N * 2 + 1], invfs[MAX_N + 1];/* subroutines */ll powmod(ll a, ll b) { // a^b % MODll pm = 1;while (b > 0) {if ((b & 1) != 0) pm = (pm * a) % MOD;a = (a * a) % MOD;b >>= 1;}return pm;}inline ll npk(int n, int k) { // nPk % MODif (n < k) return 0;return fracs[n] * invfs[n - k] % MOD;}inline ll nck(int n, int k) { // nCk % MODif (n < k) return 0;return (fracs[n] * invfs[n - k] % MOD) * invfs[k] % MOD;}inline ll nhk(int n, int k) { // nHk % MODif (k == 0) return 1;return nck(n + k - 1, k);}/* main */int main() {fracs[0] = invfs[0] = 1;for (int i = 1; i <= MAX_N * 2; i++)fracs[i] = (fracs[i - 1] * i) % MOD;for (int i = 1; i <= MAX_N; i++)invfs[i] = powmod(fracs[i], MOD - 2);int tn;cin >> tn;while (tn--) {string s;cin >> s;int n = 0, k = 0, pos = 2;while (s[pos] != ',') n = n * 10 + s[pos++] - '0';pos++;while (s[pos] != ')') k = k * 10 + s[pos++] - '0';//printf("%c(%d,%d)\n", s[0], n, k);ll ans;switch (s[0]) {case 'C': ans = nck(n, k); break;case 'P': ans = npk(n, k); break;case 'H': ans = nhk(n, k); break;}printf("%lld\n", ans);}return 0;}