結果

問題 No.117 組み合わせの数
ユーザー tkr987tkr987
提出日時 2019-09-28 05:29:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 260 ms / 5,000 ms
コード長 4,810 bytes
コンパイル時間 1,568 ms
コンパイル使用メモリ 171,872 KB
実行使用メモリ 51,312 KB
最終ジャッジ日時 2024-09-25 11:17:40
合計ジャッジ時間 2,462 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 260 ms
51,312 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 > lfact_, rfact_, inv_;

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

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

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

			rep(i, 1, vsize + 1)
				inv_[i] = rfact_[i] * lfact_[i - 1];
		}

		inline T lfact(ll k) const { return lfact_[k]; }
		inline T rfact(ll k) const { return rfact_[k]; }
		inline T inv(ll k) const { return inv_[k]; }

		T P(ll n, ll r) const
		{
			if (r < 0 || n < r) return 0;
			return lfact(n) * rfact(n - r);
		}

		T C(ll n, ll r) const
		{
			if (r < 0 || n < r) return 0;
			return lfact(n) * rfact(r) * rfact(n - r);
		}

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

namespace NyaGadget
{	// MOD ライブラリ
	using namespace std;

	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 *= (ll r)
		{
			x = (unsigned long long) x * r % 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 * (ll 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;
		}
	};

	//*******************************************
	// [sample code]
	//
	//using namespace NyaGadget;
	//using mll = ModLL<1000000007>;
	//
	//int main(void)
	//{
	//	mll x, y(1000000009);
	//  mll div_x(12345678900000);
	//  mll div_y(100000);
	//
	//	div_x /= div_y;
	//
	//	cout << "x = " << x << endl;
	//  cout << "y = " << y << endl;
	//  cout << "div_x = " << div_x << endl;
	//	return 0;
	//}
	//*******************************************
	// [output]
	//
	// x = 0
	// y = 2
	// div_x = 123456789
	//*******************************************
}

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

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

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

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

	return 0;
}
0