結果

問題 No.117 組み合わせの数
ユーザー mokomoko
提出日時 2018-03-29 13:00:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 127 ms / 5,000 ms
コード長 1,745 bytes
コンパイル時間 1,237 ms
コンパイル使用メモリ 161,320 KB
実行使用メモリ 34,548 KB
最終ジャッジ日時 2024-06-25 22:08:03
合計ジャッジ時間 2,047 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 127 ms
34,548 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:86:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |                 scanf("%1s(%lld,%lld)",ch,&n,&k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,P> PP;

//-----------------------------------------------------------------------------

template <typename T>
struct Combination {
	vector<T> fc,ifc;
	T MOD;
	int sz;

	Combination(T MOD,T sz):fc(sz+1),ifc(sz+1),MOD(MOD),sz(sz) {}

	void init() {
		fc[0]=1;
		for(int i=1;i<=sz;i++) fc[i]=fc[i-1]*i%MOD;
		ifc[sz]=inv(fc[sz]);
		for(int i=sz-1;i>=0;i--) ifc[i]=ifc[i+1]*(i+1)%MOD;
	}

	// 階乗
	T fact(int n) {
		return fc[n];
	}
	// 階乗の逆元
	T inv_fact(int n) {
		return ifc[n];
	}
	//逆元
	T inv(int n) {
		return pow(n,MOD-2);
	}
	// 冪乗
	T pow(T n,int a) {
		T res=1;
		while(a>0) {
			if(a&1) (res*=n)%=MOD;
			(n*=n)%=MOD;
			a>>=1;
		}
		return res;
	}
	// 順列
	T perm(T n,T r) {
		if(r<0||n<r) return 0;
		return fc[n]*ifc[n-r]%MOD;
	}
	// 組み合わせ
	T comb(T n,T r) {
		if(n<0||r<0||n<r) return 0;
		return fc[n]*ifc[r]%MOD*ifc[n-r]%MOD;
	}
	// 重複組み合わせ
	T multi_comb(T n,T r) {
		if(n<0||r<0) return 0;
		return r==0?1:comb(n+r-1,r);
	}
};

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);

	int t;
	cin>>t;
	Combination<ll> C((int)1e9+7,(int)1e6*2+10);
	C.init();
	while(t--) {
		char ch[10];ll n,k;
		scanf("%1s(%lld,%lld)",ch,&n,&k);
		if(ch[0]=='C') printf("%lld\n",C.comb(n,k));
		else if(ch[0]=='P') printf("%lld\n",C.perm(n,k));
		else printf("%lld\n",C.multi_comb(n,k));
	}

}
0