結果
問題 | No.3004 ヤング図形 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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}