結果

問題 No.3394 Big Binom
コンテスト
ユーザー Sinonen
提出日時 2025-12-01 10:04:58
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,186 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 901 ms
コンパイル使用メモリ 93,284 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-01 10:05:12
合計ジャッジ時間 13,795 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/**
N, K = list(map(int, input().split()))

MOD = 998244353

if K > N - K:
	K = N - K
ue = 1
sita = 1
for i in range(1, K + 1):
	ue = (ue * (N - i + 1)) % MOD
	sita = (sita * i) % MOD

sita = pow(sita, MOD - 2, MOD)

print((ue * sita) % MOD)
**/
#include <iostream>
#include <algorithm> // for std::min

using namespace std;

// MODの定義
const long long MOD = 998244353;

/**
 * @brief 繰り返し二乗法（Modular Exponentiation）
 * @param base 基数 (a)
 * @param exp 指数 (b)
 * @param mod 法 (M)
 * @return (base ^ exp) % mod
 */
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) { // 奇数の場合
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

/**
 * @brief モジュロ逆元（Modular Inverse）
 * @param n 逆元を求めたい数
 * @return n の MOD を法とする逆元 (n^(MOD-2) % MOD)
 */
long long modInverse(long long n) {
    // フェルマーの小定理により、a^(MOD-2) が逆元となる
    return power(n, MOD - 2);
}

int main() {
    // 入力の読み込み
    int N, K;
    if (!(cin >> N >> K)) return 0;

    // 二項係数 NCK = N! / (K! * (N-K)!) を計算する
    // NCK = (N * (N-1) * ... * (N-K+1)) / K!

    // K > N - K の場合、NCK = N C(N-K) の性質を利用して K を小さくする
    if (K > N - K) {
        K = N - K;
    }

    // 分子 (numerator) と分母 (denominator)
    long long ue = 1;   // N * (N-1) * ... * (N-K+1)
    long long sita = 1; // K! = K * (K-1) * ... * 1

    for (int i = 1; i <= K; ++i) {
        // 分子を計算: ue = (ue * (N - i + 1)) % MOD
        // N - i + 1 は N から始まり、N-1, N-2, ... と続く
        ue = (ue * (N - i + 1)) % MOD;

        // 分母を計算: sita = (sita * i) % MOD
        // i は 1 から K まで
        sita = (sita * i) % MOD;
    }

    // 分母 sita の逆元を求める
    long long inv_sita = modInverse(sita);

    // 最終結果 = (分子 * 分母の逆元) % MOD
    long long result = (ue * inv_sita) % MOD;

    cout << result << endl;

    return 0;
}
0