結果

問題 No.3004 ヤング図形
ユーザー titiatitia
提出日時 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
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0