結果

問題 No.117 組み合わせの数
ユーザー yuruhiyayuruhiya
提出日時 2020-07-05 10:25:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 124 ms / 5,000 ms
コード長 3,404 bytes
コンパイル時間 7,581 ms
コンパイル使用メモリ 626,088 KB
実行使用メモリ 50,416 KB
最終ジャッジ日時 2024-09-22 05:17:14
合計ジャッジ時間 8,301 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 124 ms
50,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <int MOD> struct modint {
	using T = long long;
	T n;
	constexpr modint(const T x = 0) : n(x % MOD) {
		if (n < 0) n += MOD;
	}
	constexpr int get_mod() const {
		return MOD;
	}
	constexpr modint operator+() const {
		return *this;
	}
	constexpr modint operator-() const {
		return n ? MOD - n : 0;
	}
	constexpr modint &operator++() {
		if (MOD <= ++n) n = 0;
		return *this;
	}
	constexpr modint &operator--() {
		if (n <= 0) n = MOD;
		n--;
		return *this;
	}
	constexpr modint operator++(int) {
		modint t = *this;
		++*this;
		return t;
	}
	constexpr modint operator--(int) {
		modint t = *this;
		--*this;
		return t;
	}
	constexpr modint next() const {
		return ++modint(*this);
	}
	constexpr modint pred() const {
		return --modint(*this);
	}
	constexpr modint operator+(const modint &m) const {
		return modint(*this) += m;
	}
	constexpr modint operator-(const modint &m) const {
		return modint(*this) -= m;
	}
	constexpr modint operator*(const modint &m) const {
		return modint(*this) *= m;
	}
	constexpr modint operator/(const modint &m) const {
		return modint(*this) /= m;
	}
	constexpr modint &operator+=(const modint &m) {
		n += m.n;
		if (n >= MOD) n -= MOD;
		return *this;
	}
	constexpr modint &operator-=(const modint &m) {
		n -= m.n;
		if (n < 0) n += MOD;
		return *this;
	}
	constexpr modint &operator*=(const modint &m) {
		n = n * m.n % MOD;
		return *this;
	}
	constexpr modint &operator/=(const modint &m) {
		T a = m.n, b = MOD, u = 1, v = 0;
		while (b) {
			T t = a / b;
			a -= t * b;
			swap(a, b);
			u -= t * v;
			swap(u, v);
		}
		n = n * u % MOD;
		if (n < 0) n += MOD;
		return *this;
	}
	constexpr bool operator==(const modint &m) const {
		return n == m.n;
	}
	constexpr bool operator!=(const modint &m) const {
		return n != m.n;
	}
	constexpr modint pow(T m) const {
		modint t = n, res = 1;
		while (m > 0) {
			if (m & 1) res *= t;
			t *= t;
			m >>= 1;
		}
		return res;
	}
	constexpr modint operator^(T m) const {
		return pow(m);
	}
	friend ostream &operator<<(ostream &os, const modint<MOD> &m) {
		return os << m.n;
	}
	friend istream &operator>>(istream &is, modint<MOD> &m) {
		return is >> m.n;
	}
};
using mint = modint<1000000007>;
using VM = vector<mint>;
constexpr inline mint operator""_m(unsigned long long n) {
	return n;
}

template <int MOD, size_t size> class Combi {
	using T = modint<MOD>;
	array<T, size + 1> fac, finv, inv;

public:
	constexpr Combi() {
		fac[0] = fac[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		for (size_t i = 2; i <= size; ++i) {
			fac[i] = fac[i - 1] * i;
			inv[i] = -inv[MOD % i] * (MOD / i);
			finv[i] = finv[i - 1] * inv[i];
		}
	}
	constexpr T P(int n, int r) const {
		return (n < r || n < 0 || r < 0) ? 0 : fac[n] * finv[n - r];
	}
	constexpr T C(int n, int r) const {
		return (n < r || n < 0 || r < 0) ? 0 : fac[n] * finv[r] * finv[n - r];
	}
	constexpr T H(int n, int r) const {
		return (n < 0 || r < 0) ? 0 : r == 0 ? 1 : C(n + r - 1, r);
	}
	constexpr T fact(int n) const {
		return fac[n];
	}
};

Combi<1000000007, 2000009> C;

int main() {
	int t;
	scanf("%d\n", &t);
	for (int i = 0; i < t; ++i) {
		char c;
		int n, k;
		scanf("%c(%d,%d)\n", &c, &n, &k);
		if (c == 'C') {
			printf("%lld\n", C.C(n, k).n);
		} else if (c == 'P') {
			printf("%lld\n", C.P(n, k).n);
		} else if (c == 'H') {
			printf("%lld\n", C.H(n, k).n);
		}
	}
}
0