結果

問題 No.3394 Big Binom
コンテスト
ユーザー id-ord
提出日時 2025-12-01 23:02:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,793 bytes
コンパイル時間 961 ms
コンパイル使用メモリ 88,316 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-01 23:02:04
合計ジャッジ時間 3,582 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 3 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <map>
std::map<int,int64_t> cache={{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}};
const int p=998244353;
int factorial998(int n){
	auto it=cache.upper_bound(n);it--;
	int64_t ans=it->second;
	for(int64_t i=it->first+1;i<=n;i++){
		ans*=i;
		ans%=p;
	}
	return ans;
}

int inv998(int n){
	int64_t ans=1,m=p-2;
	while(m){
		ans*=ans;
		ans%=p;
		if(m&1)ans*=n;
		ans%=p;
		m/=2;
	}
	return ans;
}
int main(){
	int N,K,k;
	std::cin>>N>>K;
	if(K<N-K)K=N-K;
	k=N-K;
	if(N>=p)if(K<p){std::cout<<0;return 0;}else N-=p;
	int64_t ans=factorial998(N);
	ans*=inv998(factorial998(K));ans%=p;
	ans*=inv998(factorial998(k));ans%=p;
	std::cout<<ans;
	return 0;
}
0