結果

問題 No.3004 ヤング図形
ユーザー magurofly
提出日時 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`

ソースコード

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 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}");
}
0