結果
問題 |
No.3004 ヤング図形
|
ユーザー |
|
提出日時 | 2025-01-17 23:10:16 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,890 ms / 4,000 ms |
コード長 | 1,429 bytes |
コンパイル時間 | 13,092 ms |
コンパイル使用メモリ | 403,916 KB |
実行使用メモリ | 392,704 KB |
最終ジャッジ日時 | 2025-01-17 23:11:17 |
合計ジャッジ時間 | 37,666 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
コンパイルメッセージ
warning: variable `K` should have a snake case name --> src/main.rs:17:5 | 17 | K: usize, | ^ help: convert the identifier to snake case (notice the capitalization): `k` | = note: `#[warn(non_snake_case)]` on by default warning: variable `C` should have a snake case name --> src/main.rs:50:7 | 50 | let C = |n, r| f(n) as usize * fi(n - r) as usize % MOD * fi(r) as usize % MOD ; | ^ help: convert the identifier to snake case (notice the capitalization): `c`
ソースコード
const MOD: usize = 998244353; fn pow(mut a: usize, mut b: usize) -> usize { let mut r = 1; while b > 0 { if b & 1 != 0 { r = r * a % MOD; } a = a * a % MOD; b >>= 1; } r } fn main() { proconio::input! { K: usize, rows: [(usize, usize); K], } let mut sum = rows.iter().map(|&(l, m)| l * m ).sum::<usize>(); sum += sum % 2; let mut fact = vec![1; sum / 2 + 1]; for i in 1 ..= sum / 2 { fact[i] = (fact[i - 1] as usize * (i * 2 - 1) % MOD * (i * 2) % MOD) as i32; } let mut fact_inv = vec![1; sum / 2 + 1]; fact_inv[sum / 2] = pow(fact[sum / 2] as usize, MOD - 2) as i32; for i in (1 .. sum / 2).rev() { fact_inv[i] = (fact_inv[i + 1] as usize * (i * 2 + 1) % MOD * (i * 2 + 2) % MOD) as i32; } let f = |n: usize| { if n % 2 == 0 { fact[n / 2] as usize } else { fact[n / 2] as usize * n % MOD } }; let fi = |n: usize| { if n % 2 == 0 { fact_inv[n / 2] as usize } else { fact_inv[n / 2 + 1] as usize * (n + 1) % MOD } }; let C = |n, r| f(n) as usize * fi(n - r) as usize % MOD * fi(r) as usize % MOD ; let mut ans = 1; let mut b = 0; for &(l, m) in rows.iter().rev() { let mut ans1 = 1; let mut a = 0; for _ in 0 .. m { a += l; ans1 = ans1 * C(a - 1, l - 1) % MOD; } ans = ans * ans1 % MOD; b += a; ans = ans * C(b, a) % MOD; } println!("{ans}"); }