結果

問題 No.3394 Big Binom
コンテスト
ユーザー Mike scarf
提出日時 2025-12-12 15:19:28
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 970 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,745 ms
コンパイル使用メモリ 276,440 KB
実行使用メモリ 35,112 KB
最終ジャッジ日時 2025-12-12 15:19:46
合計ジャッジ時間 16,023 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:44:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |     scanf("%lld %lld",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2000005;
const ll mod=998244353;
ll fac[maxn+5],ifac[maxn+5];
ll qmksm(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll ny(ll n){
    return qmksm(n,mod-2);
}
void init(){
    ll i;
    fac[0]=1;
    for(i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
    ifac[maxn]=ny(fac[maxn]);
    for(i=maxn-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}
ll C(ll n,ll k){
    if(k<0 or k>n) return 0;
    if(n<=maxn) return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
    if(k>n/2) k=n-k;
    ll a=1,b=1,i;
    for(i=1;i<=k;i++){
        a=a*((n-i+1)%mod)%mod;
        b=b*i%mod;
    }
    return a*ny(b)%mod;
}
ll lucas(ll n,ll k){
    if(k==0) return 1;
    return lucas(n/mod,k/mod)*C(n%mod,k%mod)%mod;
}
int main(){
    ll n,k,ans;
    init();
    scanf("%lld %lld",&n,&k);
    ans=lucas(n,k);
    printf("%lld\n",ans);
    return 0;
}
0