結果

問題 No.117 組み合わせの数
コンテスト
ユーザー kazuma
提出日時 2018-03-10 12:11:09
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 74 ms / 5,000 ms
コード長 2,091 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,266 ms
コンパイル使用メモリ 193,484 KB
最終ジャッジ日時 2025-01-05 09:14:10
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

template<int MOD>
struct mod_int {
	static const int mod = MOD;
	unsigned x;
	mod_int() : x(0) { }
	mod_int(int sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	mod_int(long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	mod_int &operator+=(mod_int that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator-=(mod_int that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	mod_int &operator*=(mod_int that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	mod_int &operator/=(mod_int that) { return *this *= that.inverse(); }

	mod_int operator+(mod_int that) const { return mod_int(*this) += that; }
	mod_int operator-(mod_int that) const { return mod_int(*this) -= that; }
	mod_int operator*(mod_int that) const { return mod_int(*this) *= that; }
	mod_int operator/(mod_int that) const { return mod_int(*this) /= that; }

	mod_int inverse() 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 mod_int(u);
	}
};

const int mod = 1e9 + 7;

using mint = mod_int<mod>;

const int MAX = 2e6;

mint fac[MAX + 1];
mint rfac[MAX + 1];

void init() {
	fac[0] = 1;
	for (int i = 1; i <= MAX; i++) {
		fac[i] = fac[i - 1] * i;
	}
	rfac[MAX] = fac[MAX].inverse();
	for (int i = MAX; i >= 1; i--) {
		rfac[i - 1] = rfac[i] * i;
	}
}

mint nPr(int n, int r) {
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r];
}

mint nCr(int n, int r) {
	return r < 0 || n < r ? 0 : fac[n] * rfac[n - r] * rfac[r];
}

mint nHr(int n, int r) {
	return r == 0 ? 1 : nCr(n + r - 1, r);
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	init();
	int T;
	cin >> T;
	while (T--) {
		char com, c;
		int n, r;
		cin >> com >> c >> n >> c >> r >> c;
		if (com == 'P') {
			printf("%d\n", nPr(n, r).get());
		}
		else if (com == 'C') {
			printf("%d\n", nCr(n, r).get());
		}
		else {
			printf("%d\n", nHr(n, r).get());
		}
	}
	return 0;
}
0