結果

問題 No.117 組み合わせの数
コンテスト
ユーザー y61mpnl
提出日時 2021-06-13 17:12:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 156 ms / 5,000 ms
コード長 968 bytes
コンパイル時間 468 ms
コンパイル使用メモリ 49,536 KB
最終ジャッジ日時 2025-01-22 07:58:45
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:37:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~
main.cpp:45:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |                 scanf("(%d,%d)", &n, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<cstdio>
#include<cstdint>
#include<vector>

const int MOD = 1e9 + 7;

template<typename Int>
struct Combination {
	std::vector<Int> fac, inv, finv;
	Combination(int n=1e6): fac(n), inv(n), finv(n) {
		fac[0] = fac[1] = inv[1] = finv[0] = finv[1] = 1;
		for(Int i=2; i<n; i++){
			fac[i] = fac[i-1] * i % MOD;
			inv[i] = (-MOD/i + MOD) * inv[MOD%i] % MOD;
			finv[i] = finv[i-1] * inv[i] % MOD;
		}
	}

	Int C(Int n, Int k){
		if(n==k || k==0) return 1;
		if(n<0 || k<0 || n<k) return 0;
		return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
	}

	Int P(Int n, Int k){
		return C(n, k) * fac[k] % MOD;
	}

	Int H(Int n, Int k){
		return C(n+k-1, k);
	}
};


int main(){
	int t;
	scanf("%d", &t);

	Combination<int64_t> com(2e6);

	while(t--){
		getchar();
		char c = getchar();
		int n, k;
		scanf("(%d,%d)", &n, &k);
		if(c=='C') printf("%ld\n", com.C(n, k));
		if(c=='P') printf("%ld\n", com.P(n, k));
		if(c=='H') printf("%ld\n", com.H(n, k));
	}
	return 0;
}
0