結果

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

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define srep(i,l,r) for(ll i=l;i<=r;i++)
#define irep(i,r,l) for(ll i=r;i>=l;i--)
using ll = long long;
using ld = long double;
const ll mod=998244353;
#define vout(v) for(auto i :v) cout<<i<<" ";  cout<<nl;
#define INF 9223300000000000000ll
#define Winf 5e12
#define nl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vl vector<ll>
#define pb push_back
#define vc vector<char>
#define vb vector<bool>
#define uniq(x) sort((x).begin(),(x).end());(x).erase(unique((x).begin(),(x).end()),(x).end())
#define eb emplace_back



void no(void) { cout<<"No"<<nl;}
void yes(void) {cout<<"Yes"<<nl;}
void yn(bool a) {
    cout<<(a ? "Yes":"No")<<nl;
}


vector<ll> dx={-1,0,1,0,1,1,-1,-1};
vector<ll> dy={0,-1,0,1,-1,1,-1,1};

bool isin(ll i,ll j,ll h,ll w) {
    if(i<0 || i>=h || j<0 || j>=w) return false;
    return true;
}

template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}


template<class T>T vecmax(const vector<T>&v){return *max_element(all(v));}
template<class T>T vecmin(const vector<T>&v){return *min_element(all(v));}

ll safemod(ll num,ll rule) {
    return (num%rule+rule)%rule;
}

ll sum(vector<ll> &a) {
    return accumulate(all(a),0ll);
}
template<class T>void vvpr(vector<vector<T>> g) {
    rep(i,g.size()) {
        rep(j,g[i].size()) {
            cout<<g[i][j]<<(j==g[i].size()-1 ? "\n":" ");
        }
    }
}
ll calcfact(unordered_map<ll,ll>& fact,ll n) {
    ll near;
    near=n/10000000*10000000;
    ll nfact=fact[near];
    srep(i,near+1,n) {
        nfact*=i;
        nfact%=mod;
    }
    return nfact;
}
#define MOD 998244353
template<class T> T modpow(T fl, ll po, ll mode) {  // mode: 0=modなし, 1=modあり
    assert(po>=0);
    T ret(1);
    if (mode) {
        fl%=T(MOD);
        while (po>0) {
            if (po&1) ret=(ret*fl)%T(MOD);
            fl=(fl*fl)%T(MOD);
            po>>=1;
        }
    } else {
        while (po>0) {
            if(po&1) ret*=fl;
            fl*=fl;
            po>>=1;
        }
    }
    return ret;
}
int main() {
    unordered_map<ll,ll> fact;
    fact[0]=1;
    fact[10000000]=295201906;
    fact[20000000]=160030060;
    fact[30000000]=957629942;
    fact[40000000]=545208507;
    fact[50000000]=213689172;
    fact[60000000]=760025067;
    fact[70000000]=939830261;
    fact[80000000]=506268060;
    fact[90000000]=39806322;
    fact[100000000]=808258749;
    fact[110000000]=440133909;
    fact[120000000]=686156489;
    fact[130000000]=741797144;
    fact[140000000]=390377694;
    fact[150000000]=12629586;
    fact[160000000]=544711799;
    fact[170000000]=104121967;
    fact[180000000]=495867250;
    fact[190000000]=421290700;
    fact[200000000]=117153405;
    fact[210000000]=57084755;
    fact[220000000]=202713771;
    fact[230000000]=675932866;
    fact[240000000]=79781699;
    fact[250000000]=956276337;
    fact[260000000]=652678397;
    fact[270000000]=35212756;
    fact[280000000]=655645460;
    fact[290000000]=468129309;
    fact[300000000]=761699708;
    fact[310000000]=533047427;
    fact[320000000]=287671032;
    fact[330000000]=206068022;
    fact[340000000]=50865043;
    fact[350000000]=144980423;
    fact[360000000]=111276893;
    fact[370000000]=259415897;
    fact[380000000]=444094191;
    fact[390000000]=593907889;
    fact[400000000]=573994984;
    fact[410000000]=892454686;
    fact[420000000]=566073550;
    fact[430000000]=128761001;
    fact[440000000]=888483202;
    fact[450000000]=251718753;
    fact[460000000]=548033568;
    fact[470000000]=428105027;
    fact[480000000]=742756734;
    fact[490000000]=546182474;
    fact[500000000]=62402409;
    fact[510000000]=102052166;
    fact[520000000]=826426395;
    fact[530000000]=159186619;
    fact[540000000]=926316039;
    fact[550000000]=176055335;
    fact[560000000]=51568171;
    fact[570000000]=414163604;
    fact[580000000]=604947226;
    fact[590000000]=681666415;
    fact[600000000]=511621808;
    fact[610000000]=924112080;
    fact[620000000]=265769800;
    fact[630000000]=955559118;
    fact[640000000]=763148293;
    fact[650000000]=472709375;
    fact[660000000]=19536133;
    fact[670000000]=860830935;
    fact[680000000]=290471030;
    fact[690000000]=851685235;
    fact[700000000]=242726978;
    fact[710000000]=169855231;
    fact[720000000]=612759169;
    fact[730000000]=599797734;
    fact[740000000]=961628039;
    fact[750000000]=953297493;
    fact[760000000]=62806842;
    fact[770000000]=37844313;
    fact[780000000]=909741023;
    fact[790000000]=689361523;
    fact[800000000]=887890124;
    fact[810000000]=380694152;
    fact[820000000]=669317759;
    fact[830000000]=367270918;
    fact[840000000]=806951470;
    fact[850000000]=843736533;
    fact[860000000]=377403437;
    fact[870000000]=945260111;
    fact[880000000]=786127243;
    fact[890000000]=80918046;
    fact[900000000]=875880304;
    fact[910000000]=364983542;
    fact[920000000]=623250998;
    fact[930000000]=598764068;
    fact[940000000]=804930040;
    fact[950000000]=24257676;
    fact[960000000]=214821357;
    fact[970000000]=791011898;
    fact[980000000]=954947696;
    fact[990000000]=183092975;
    fact[1000000000]=0;
    ll n,k; cin>>n>>k;
    ll n0=n%mod,n1=n/mod;
    ll k0=k%mod,k1=k/mod;
    ll cont=1;
    if(n1 && k1) cont=1;
    if(n1 && !k1) cont=1;
    if(n0<k0) {
        cout<<0<<nl;
        return 0;
    }
    ll nfact=calcfact(fact,n0);
    ll kfact=calcfact(fact,k0);
    ll nmkfact=calcfact(fact,n0-k0);
    ll ans=nfact;
    ans*=modpow(kfact,998244351,1);
    ans%=mod;
    ans*=modpow(nmkfact,998244351,1);
    ans%=mod;
    ans*=cont;
    ans%=mod;
    cout<<ans<<nl;
}
0