結果

問題 No.3394 Big Binom
コンテスト
ユーザー Sinonen
提出日時 2025-12-01 10:12:33
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,850 ms / 2,000 ms
コード長 2,193 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 22,733 ms
コンパイル使用メモリ 399,356 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-12-01 10:13:08
合計ジャッジ時間 25,074 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
元のPythonコード:

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)
*/

use std::io;
use std::cmp;

// MODの定数定義
const MOD: u64 = 998244353;

// --- 補助関数 (Pythonの pow(..., MOD) の代わり) ---

/**
 * 繰り返し二乗法 (Modular Exponentiation)
 * (base ^ exp) % MOD を計算します。
 */
fn power(mut base: u64, mut exp: u64) -> u64 {
    let mut res = 1;
    base %= MOD;
    while exp > 0 {
        if exp % 2 == 1 {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    res
}

/**
 * モジュロ逆元 (Modular Inverse)
 * フェルマーの小定理により n^(MOD-2) % MOD を計算します。
 */
fn mod_inverse(n: u64) -> u64 {
    // MOD-2 乗することで逆元が得られます
    power(n, MOD - 2)
}

// --- メイン処理 ---

fn main() {
    // 標準入力から1行読み込み (N, K)
    let mut line = String::new();
    io::stdin().read_line(&mut line).expect("Failed to read line");

    // N, K = list(map(int, input().split()))
    let parts: Vec<u64> = line
        .split_whitespace()
        .filter_map(|s| s.parse().ok())
        .collect();

    if parts.len() < 2 {
        return;
    }

    let n = parts[0];
    let mut k = parts[1];

    // if K > N - K: K = N - K
    // NCK = N C(N-K) の性質を利用し、Kを小さくする
    k = cmp::min(k, n - k);

    // ue = 1, sita = 1
    let mut ue: u64 = 1;   // 分子: N * (N-1) * ... * (N-K+1)
    let mut sita: u64 = 1; // 分母: K!

    // for i in range(1, K + 1):
    for i in 1..=k {
        // ue = (ue * (N - i + 1)) % MOD
        ue = (ue * (n - i + 1)) % MOD;

        // sita = (sita * i) % MOD
        sita = (sita * i) % MOD;
    }

    // sita = pow(sita, MOD - 2, MOD)
    // 分母 sita の逆元を求める
    let inv_sita = mod_inverse(sita);

    // print((ue * sita) % MOD)
    // 結果 = (分子 * 分母の逆元) % MOD
    let result = (ue * inv_sita) % MOD;

    println!("{}", result);
}
0