結果
問題 | No.117 組み合わせの数 |
ユーザー |
![]() |
提出日時 | 2019-08-19 16:51:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 5,000 ms |
コード長 | 3,062 bytes |
コンパイル時間 | 642 ms |
コンパイル使用メモリ | 72,708 KB |
実行使用メモリ | 32,772 KB |
最終ジャッジ日時 | 2024-10-04 14:45:18 |
合計ジャッジ時間 | 1,073 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>using namespace std;const int MOD = (int)1e9 + 7;//---------------------------------------------------------------template<int MOD> struct ModInt { int x;explicit operator bool() const { return !!x; }ModInt(int v = 0) : x(v % MOD) { if (x < 0) x += MOD; }ModInt(long long v) : x(v % MOD) { if (x < 0) x += MOD; }ModInt &operator+=(const ModInt &r) { if ((x += r.x) >= MOD) x -= MOD; return *this; }ModInt &operator-=(const ModInt &r) { if ((x += MOD - r.x) >= MOD) x -= MOD; return *this; }ModInt &operator*=(const ModInt &r) { x = 1LL * x * r.x % MOD; return *this; }ModInt &operator/=(const ModInt &r) { return *this *= r.inv(); }ModInt operator-() const { return x ? ModInt(MOD - x) : ModInt(x); }ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }ModInt inv() const { long long a = x, b = MOD, u = 1, v = 0;while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }return ModInt(u); } // x.pow(MOD-2)ModInt pow(long long k) const { ModInt r(1), a(x);while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }bool operator==(const ModInt r) const { return x == r.x; }bool operator!=(const ModInt r) const { return x != r.x; }bool operator< (const ModInt r) const { return x < r.x; }friend ostream& operator<<(ostream &os, const ModInt<MOD>& a) { return os << a.x; }friend istream& operator>>(istream &is, ModInt<MOD>& a) { return is >> a.x; }};template<typename T, int SZ> struct Comb { vector<T> _fac, _ifac, _inv;Comb() : _fac(SZ + 1), _ifac(SZ + 1), _inv(SZ + 1) {_fac[0] = _ifac[SZ] = _inv[0] = 1;for (int i = 1; i <= SZ; i++) _fac[i] = _fac[i - 1] * i;_ifac[SZ] /= _fac[SZ];for (int i = SZ - 1; i >= 0; i--) _ifac[i] = _ifac[i + 1] * (i + 1);for (int i = 1; i <= SZ; i++) _inv[i] = _ifac[i] * _fac[i - 1]; }T inv(int n) { return n < 0 ? T(0) : _inv[n]; }T fac(int n) { return n < 0 ? T(0) : _fac[n]; }T ifac(int n) { return n < 0 ? T(0) : _ifac[n]; }T P(int a, int b) { return (b < 0 || a < b) ? T(0) : _fac[a] * _ifac[a - b]; }T C(int a, int b) { return b < 0 ? T(0) : P(a, b) * _ifac[b]; }T H(int n, int k) { if (n < 0 || k < 0) return T(0);return k == 0 ? T(1) : C(n + k - 1, k); }};typedef ModInt<MOD> mint;//---------------------------------------------------------------int main() {Comb<mint, 2500000> com;int T; scanf("%d\n", &T);while (T--) {char c; int n, k;scanf("%c(%d,%d)\n", &c, &n, &k);if (c == 'C') printf("%d\n", com.C(n, k).x);if (c == 'P') printf("%d\n", com.P(n, k).x);if (c == 'H') printf("%d\n", com.H(n, k).x);}return 0;}