結果

問題 No.3004 ヤング図形
ユーザー magurofly
提出日時 2025-01-17 22:56:36
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 1,065 bytes
コンパイル時間 12,992 ms
コンパイル使用メモリ 378,368 KB
実行使用メモリ 783,360 KB
最終ジャッジ日時 2025-01-17 22:57:35
合計ジャッジ時間 40,400 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 MLE * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:33:7
   |
33 |   let C = |n, r| fact[n] as usize * fact_inv[n - r] as usize % MOD * fact_inv[r] as usize % MOD ;
   |       ^ help: convert the identifier to snake case (notice the capitalization): `c`

ソースコード

diff # 

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 sum = rows.iter().map(|&(l, m)| l * m ).sum::<usize>();

  let mut fact = vec![1; sum + 1];
  for i in 1 ..= sum {
    fact[i] = (fact[i - 1] as usize * i % MOD) as i32;
  }

  let mut fact_inv = vec![1; sum + 1];
  fact_inv[sum] = pow(fact[sum] as usize, MOD - 2) as i32;
  for i in (1 .. sum).rev() {
    fact_inv[i] = (fact_inv[i + 1] as usize * (i + 1) % MOD) as i32;
  }

  let C = |n, r| fact[n] as usize * fact_inv[n - r] as usize % MOD * fact_inv[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}");
}
0