結果

問題 No.3004 ヤング図形
コンテスト
ユーザー titia
提出日時 2025-01-17 23:10:08
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,944 bytes
コンパイル時間 13,659 ms
コンパイル使用メモリ 400,532 KB
実行使用メモリ 820,004 KB
最終ジャッジ日時 2025-01-17 23:12:00
合計ジャッジ時間 99,538 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 14 MLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::BTreeMap;
use std::io;

const MOD: u64 = 998244353;

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let k: usize = input.trim().parse().unwrap();

    let mut lm = Vec::new();
    for _ in 0..k {
        input.clear();
        io::stdin().read_line(&mut input).unwrap();
        let nums: Vec<u64> = input
            .trim()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect();
        lm.push((nums[0], nums[1]));
    }

    let mut k_vec = Vec::new();
    for &(l, m) in &lm {
        k_vec.push(l * m);
    }

    let mut ans: u64 = 1;
    let mut sum: u64 = k_vec.iter().sum();

    let mut plus: BTreeMap<u64, u64> = BTreeMap::new();
    let mut inv: BTreeMap<u64, u64> = BTreeMap::new();

    for &k in &k_vec {
        *plus.entry(sum).or_insert(0) += 1;
        *inv.entry(sum - k).or_insert(0) += 1;
        *inv.entry(k).or_insert(0) += 1;
        sum -= k;
    }

    for &(l, m) in &lm {
        let mut sum = l * m;
        for _ in 0..m {
            *plus.entry(sum).or_insert(0) += 1;
            *inv.entry(sum - l).or_insert(0) += 1;
            *inv.entry(l).or_insert(0) += 1;
            sum -= l;
        }
        *inv.entry(m).or_insert(0) += 1;
    }

    let mut f: u64 = 1;
    for i in 1..=k_vec.iter().sum::<u64>() {
        f = f * i % MOD;
        if let Some(&count) = plus.get(&i) {
            ans = ans * mod_pow(f, count, MOD) % MOD;
        }
        if let Some(&count) = inv.get(&i) {
            ans = ans * mod_pow(mod_pow(f, count, MOD), MOD - 2, MOD) % MOD;
        }
    }

    println!("{}", ans % MOD);
}

fn mod_pow(mut base: u64, mut exp: u64, modu: u64) -> u64 {
    let mut result = 1;
    base %= modu;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % modu;
        }
        base = base * base % modu;
        exp /= 2;
    }
    result
}
0