結果

問題 No.3394 Big Binom
コンテスト
ユーザー daiota
提出日時 2025-12-01 19:52:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,565 bytes
記録
コンパイル時間 1,951 ms
コンパイル使用メモリ 197,984 KB
実行使用メモリ 245,752 KB
最終ジャッジ日時 2025-12-01 19:53:13
合計ジャッジ時間 36,556 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 WA * 1 TLE * 4 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i=0;i<ll(n);i++)





const ll MOD=998244353;
ll inv[10000010],fac[10000010],finv[10000010];

void fact(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(ll i=2;i<10000005;i++){
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]* i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}

ll C(ll n,ll k){
	if(!(0<=k && k<=n)) return 0;
	return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}


ll mp(ll x,ll n){
    ll res=1;
    while(n!=0LL){
	if(n%2!=0LL) res=(res*x)%MOD;
	x=(x*x)%MOD;
	n/=2;
   }
    return res;
}




int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	ll i,j;




	fact();


	vector<ll> v={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};
	vector<ll> u={1,238444764,130745802,444161914,63167040,807417660,201172540,436956075,423644083,679183929,819876469,217902006,79495400,282194932,625767044,72235345,27538317,951975633,706400183,377211807,632272425,978110840,259434518,807987027,121047638,236925172,445468955,838907796,671698386,750243457,307193889,889412629,731331257,744205788,314900522,411534515,139400499,224964707,276235118,7465234,278597952,745336996,158169460,597793402,419138882,33421630,843341534,106712971,957664621,846900234,990374204,711091584,26308095,206253917,714130259,914227850,482075393,968566300,990409070,448948773,782780334,624653049,34192879,775681124,854160346,99834634,830285621,840961969,458086537,975054410,343976104,621815256,25624980,296147014,297906019,355835632,709078571,103561614,526326842,626895307,838298556,359279113,626697572,144764408,575689639,430609208,616788059,649530258,717481494,428087505,60564204,879228478,651391373,126859812,707467502,10844499,461773889,490372001,337416158,977948258};



	ll N,K;
	cin >> N >> K;


	ll x=1;
	if(N<=10000000) cout << C(N,K) << endl;
	else if(N+1-K>MOD){

			for(i=N+1-K;i<=N;i++){
				x=x*i%MOD;
			}

			x*=finv[K];
			x%=MOD;

			cout << x << endl;

	}
	else if(K+1>MOD){

		K=N-K;
			for(i=N+1-K;i<=N;i++){
				x=x*i%MOD;
			}

			x*=finv[K];
			x%=MOD;

			cout << x << endl;

	}

	else{

		ll p=N/10000000;
		x=v[p];
		for(i=10000000*p+1;i<=N;i++){
			x*=i;
			x%=MOD;
		}


		ll q=K/10000000;
		ll y=u[q];
		if(K<=10000000){
			x*=finv[K];
			x%=MOD;
		}else{
			for(i=10000000*q+1;i<=K;i++){
				j=mp(i,MOD-2);
				y=y*j%MOD;
			}
			x*=y;
			x%=MOD;
		}


		q=(N-K)/10000000;
		y=u[q];
		if(N-K<=10000000){
			x*=finv[N-K];
			x%=MOD;
		}else{
			for(i=10000000*q+1;i<=N-K;i++){
				j=mp(i,MOD-2);
				y=y*j%MOD;
			}
			x*=y;
			x%=MOD;
		}



		cout << x << endl;


	}










	return 0;

}
0