結果

問題 No.117 組み合わせの数
ユーザー tkr987tkr987
提出日時 2019-09-28 14:15:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 264 ms / 5,000 ms
コード長 4,026 bytes
コンパイル時間 1,840 ms
コンパイル使用メモリ 172,184 KB
実行使用メモリ 51,316 KB
最終ジャッジ日時 2024-10-02 05:37:16
合計ジャッジ時間 2,854 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection) (collection).begin(), (collection).end()  // begin to end
#define each(e, collection) for(auto& e: collection)              // for each
#define rep(i, begin, end) for (ll i = begin; i < end; i++)       // repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)      // repeat reverse
#define size(collection) ((ll) (collection).size())               // collection size

#endif

namespace NyaGadget
{	// 数え上げライブラリ(引数にModライブラリなどを渡すことを想定)
	template< typename T > struct Counting
	{
		vector< T > fv, fvinv, inv;

		Counting(ll maxsize)
		{	// Hがn+r-1なので、vsizeをmaxsize * 2とする
			ll vsize = maxsize * 2;
			fv.resize(vsize + 1);
			fvinv.resize(vsize + 1);
			inv.resize(vsize + 1);
			fv[0] = fvinv[vsize] = inv[0] = 1;

			T mi;
			rep(i, 1, vsize + 1)
			{
				mi = i;
				fv[i] = mi * fv[i - 1];
			}
			fvinv[vsize] /= fv[vsize];

			repr(i, vsize - 1, -1)
			{
				mi = i;
				fvinv[i] = (mi + 1) * fvinv[i + 1];
			}

			rep(i, 1, vsize + 1)
				inv[i] = fvinv[i] * fv[i - 1];
		}

		T Factorial(ll k) { return fv[k]; }
		T FactorialInv(ll k) { return fvinv[k]; }
		T Inv(ll k) { return inv[k]; }

		T P(ll n, ll r)
		{
			if (r < 0 || n < r)
				return 0;
			return Factorial(n) * FactorialInv(n - r);
		}

		T C(ll n, ll r)
		{
			if (r < 0 || n < r)
				return 0;
			return Factorial(n) * FactorialInv(r) * FactorialInv(n - r);
		}

		T H(ll n, ll r)
		{
			if (n < 0 || r < 0)
				return 0;
			return r == 0 ? 1 : C(n + r - 1, r);
		}
	};
}

namespace NyaGadget
{	// MOD ライブラリ
	template<long long mod> struct ModLL
	{
		long long x;

		// コンストラクタ
		ModLL()
		{
			x = 0;
		}
		ModLL(long long x_)
		{
			x = x_ % mod + mod;
			if (x >= mod)
				x -= mod;
		}

		// 符号
		ModLL operator + () const { return x; }
		ModLL operator - () const { return (-x < 0) ? mod - x : -x; }

		// 加減乗除演算子
		ModLL& operator += (ModLL r)
		{
			if ((x += r.x) >= mod)
				x -= mod;
			return *this;
		}
		ModLL& operator -= (ModLL r)
		{
			if ((x -= r.x) < 0)
				x += mod;
			return *this;
		}
		ModLL& operator *= (ModLL r)
		{
			x = (unsigned long long) x * r.x % mod;
			return *this;
		}
		ModLL& operator /= (ModLL r)
		{
			x = x * Inv(r.x, mod) % mod;
			return *this;
		}

		ModLL operator + (ModLL r) const { return ModLL(*this) += r; }
		ModLL operator - (ModLL r) const { return ModLL(*this) -= r; }
		ModLL operator * (ModLL r) const { return ModLL(*this) *= r; }
		ModLL operator / (ModLL r) const { return ModLL(*this) /= r; }

		// 逆元 x^{-1} (主に除算演算子で使用)
		long long Inv(long long a, long long m)
		{
			long long b = m, u = 1, v = 0;

			while (b)
			{
				long long t = a / b;
				a -= t * b; swap(a, b);
				u -= t * v; swap(u, v);
			}

			u %= m;

			return (u < 0) ? u + m : u;
		}

		// 比較演算子
		bool operator == (ModLL& r) const { return x == r.x; }
		bool operator != (ModLL& r) const { return x != r.x; }
		bool operator <  (ModLL& r) const { return x < r.x; }
		bool operator <= (ModLL& r) const { return x <= r.x; }
		bool operator >  (ModLL& r) const { return x > r.x; }
		bool operator >= (ModLL& r) const { return x >= r.x; }

		// 入出力演算子
		friend ostream& operator << (ostream& s, ModLL<mod> a)
		{
			s << a.x;
			return s;
		}
		friend istream& operator >> (istream& s, ModLL<mod>& a)
		{
			s >> a.x;
			return s;
		}
	};
}

using namespace NyaGadget;
using mll = ModLL<1000000007>;

int main(void)
{
	char type, buff;
	ll n, r;

	ll t; cin >> t;
	vector<mll> ans;
	Counting<mll> count(1000000);
	rep(i, 0, t)
	{
		cin >> type >> buff >> n >> buff >> r >> buff;
		if (type == 'C')
			ans.push_back(count.C(n, r));
		else if (type == 'P')
			ans.push_back(count.P(n, r));
		else
			ans.push_back(count.H(n, r));
	}

	each(e, ans)
		cout << e << endl;

	return 0;
}
0