結果

問題 No.3394 Big Binom
コンテスト
ユーザー kotatsugame
提出日時 2025-12-01 00:49:48
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 1,825 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 509 ms
コンパイル使用メモリ 68,088 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-14 19:58:47
合計ジャッジ時間 2,383 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<cassert>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
const int W=1e7;
mint fac[mint::mod()/W+1]={1,295201906,160030060,957629942,545208507,213689172,760025067,939830261,506268060,39806322,808258749,440133909,686156489,741797144,390377694,12629586,544711799,104121967,495867250,421290700,117153405,57084755,202713771,675932866,79781699,956276337,652678397,35212756,655645460,468129309,761699708,533047427,287671032,206068022,50865043,144980423,111276893,259415897,444094191,593907889,573994984,892454686,566073550,128761001,888483202,251718753,548033568,428105027,742756734,546182474,62402409,102052166,826426395,159186619,926316039,176055335,51568171,414163604,604947226,681666415,511621808,924112080,265769800,955559118,763148293,472709375,19536133,860830935,290471030,851685235,242726978,169855231,612759169,599797734,961628039,953297493,62806842,37844313,909741023,689361523,887890124,380694152,669317759,367270918,806951470,843736533,377403437,945260111,786127243,80918046,875880304,364983542,623250998,598764068,804930040,24257676,214821357,791011898,954947696,183092975,};
mint factorial(int n)
{
	assert(n<mint::mod());
	mint x=fac[n/W];
	for(int i=n/W*W+1;i<=n;i++)x*=mint::raw(i);
	return x;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	if(false)
	{
		cout<<"1,";
		mint x=1;
		for(int n=1;n<mint::mod();n++)
		{
			x*=mint::raw(n);
			if(n%W==0)cout<<x.val()<<",";
		}
		cout<<endl;
		return 0;
	}
	int N,K;
	cin>>N>>K;
	if(N-K<K)K=N-K;
	if(N>=mint::mod())
	{
		if(N-K>=mint::mod())
		{
			mint x=1;
			for(int i=1;i<=K;i++)x*=mint(N-i+1);
			mint y=1;
			for(int i=1;i<=K;i++)y*=mint::raw(i);
			cout<<(x/y).val()<<endl;
		}
		else cout<<"0\n";
	}
	else
	{
		cout<<(factorial(N)/(factorial(K)*factorial(N-K))).val()<<"\n";
	}
}
0