結果

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

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define long long long
#define INF 1000000001
#define MOD 998244353
using namespace std;

vector<long> preCal = {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,0};

long power(int a, int b)
{
    if(b == 0)
        return 1;
    if(b == 1)
        return a;
    
    long c = power(a,b/2);
    c = c*c%MOD;

    if(b&1)
        return c*a%MOD;
    return c;
}
long modinv(int x)
{
    return power(x,MOD-2);
}


long fac(int x)
{
    long cur = preCal[x/10000000];
    int q = x%10000000;

    for(int i = x-q+1; i<=x; i++)
    {
        cur*=i;
        cur%=MOD;
    }
    return cur;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    k = min(k,n-k);
    if(n-k >= MOD)
    {
        long top = 1;
        long down = 1;
        for(int i = 0; i<k; i++)
            top = top*(n-i)%MOD;
        for(int i = 1; i<=k; i++)
            down = down*i%MOD;
        cout << top*modinv(down)%MOD << endl;
    }
    else
        cout << fac(n)*modinv(fac(n-k)*fac(k)%MOD)%MOD << endl;
    return 0;
}
0