結果

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

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------

int N,K;
const ll mo=998244353;

ll fact(ll N) {
	/*
	ll p=1;
	cout<<"0,1"<<endl;
	for(i=1;i<=mo+100000000;i++) {
		p=p*i%mo;
		if(i%10000000==0) cout<<i<<","<<p<<endl;
	}
	*/

	vector<pair<int,ll>> V= {
		{0,1},
		{10000000,295201906},
		{20000000,160030060},
		{30000000,957629942},
		{40000000,545208507},
		{50000000,213689172},
		{60000000,760025067},
		{70000000,939830261},
		{80000000,506268060},
		{90000000,39806322},
		{100000000,808258749},
		{110000000,440133909},
		{120000000,686156489},
		{130000000,741797144},
		{140000000,390377694},
		{150000000,12629586},
		{160000000,544711799},
		{170000000,104121967},
		{180000000,495867250},
		{190000000,421290700},
		{200000000,117153405},
		{210000000,57084755},
		{220000000,202713771},
		{230000000,675932866},
		{240000000,79781699},
		{250000000,956276337},
		{260000000,652678397},
		{270000000,35212756},
		{280000000,655645460},
		{290000000,468129309},
		{300000000,761699708},
		{310000000,533047427},
		{320000000,287671032},
		{330000000,206068022},
		{340000000,50865043},
		{350000000,144980423},
		{360000000,111276893},
		{370000000,259415897},
		{380000000,444094191},
		{390000000,593907889},
		{400000000,573994984},
		{410000000,892454686},
		{420000000,566073550},
		{430000000,128761001},
		{440000000,888483202},
		{450000000,251718753},
		{460000000,548033568},
		{470000000,428105027},
		{480000000,742756734},
		{490000000,546182474},
		{500000000,62402409},
		{510000000,102052166},
		{520000000,826426395},
		{530000000,159186619},
		{540000000,926316039},
		{550000000,176055335},
		{560000000,51568171},
		{570000000,414163604},
		{580000000,604947226},
		{590000000,681666415},
		{600000000,511621808},
		{610000000,924112080},
		{620000000,265769800},
		{630000000,955559118},
		{640000000,763148293},
		{650000000,472709375},
		{660000000,19536133},
		{670000000,860830935},
		{680000000,290471030},
		{690000000,851685235},
		{700000000,242726978},
		{710000000,169855231},
		{720000000,612759169},
		{730000000,599797734},
		{740000000,961628039},
		{750000000,953297493},
		{760000000,62806842},
		{770000000,37844313},
		{780000000,909741023},
		{790000000,689361523},
		{800000000,887890124},
		{810000000,380694152},
		{820000000,669317759},
		{830000000,367270918},
		{840000000,806951470},
		{850000000,843736533},
		{860000000,377403437},
		{870000000,945260111},
		{880000000,786127243},
		{890000000,80918046},
		{900000000,875880304},
		{910000000,364983542},
		{920000000,623250998},
		{930000000,598764068},
		{940000000,804930040},
		{950000000,24257676},
		{960000000,214821357},
		{970000000,791011898},
		{980000000,954947696},
		{990000000,183092975},
		{1000000000,0},
	};
	int i;
	int cur=0;
	ll v=1;
	FOR(i,V.size()) if(N>=V[i].first) cur=V[i].first,v=V[i].second;
	while(cur<N) v=v*++cur%mo;
	return v;
	
}
	

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	K=min(K,N-K);
	
	if(N>=mo) {
		ll p=1;
		ll q=1;
		for(i=1;i<=K;i++) {
			p=p*(N+1-i)%mo;
			q=q*i%mo;
			if(p==0) break;
		}
		p=p*modpow(q)%mo;
		cout<<p<<endl;
		return;
	}
	ll a=fact(N);
	ll b=fact(K);
	ll c=fact(N-K);
	cout<<a*modpow(b*c%mo)%mo<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}
0