結果
問題 | No.3004 ヤング図形 |
ユーザー |
|
提出日時 | 2025-01-18 09:48:01 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 550 ms / 4,000 ms |
コード長 | 2,192 bytes |
コンパイル時間 | 22,869 ms |
コンパイル使用メモリ | 375,188 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-18 09:48:36 |
合計ジャッジ時間 | 25,688 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#[allow(unused_imports)]use std::{collections::*,cmp::*,mem::swap,time::Instant,io::{self, stdin, Read, read_to_string},hash::Hash,};#[allow(unused_imports)]use proconio::{input, input_interactive, marker::{*}};#[allow(unused_imports)]//use rand::{thread_rng, Rng, seq::SliceRandom};#[allow(unused_imports)]//use ac_library::{*};#[allow(dead_code)]const INF: i64 = 1<<60;#[allow(dead_code)]const MOD: i64 = 998244353;#[allow(dead_code)]const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)];pub fn floor(a:i64, b:i64)->i64{let res=(a%b+b)%b;(a-res)/b}pub fn extended_gcd(a:i64,b:i64)->(i64,i64,i64){if b==0{(a,1,0)}else{let(g,x,y)=extended_gcd(b,a%b);(g,y,x-floor(a,b)*y)}}pub fn mod_inverse(a:i64,m:i64)->i64{let(_,x,_) =extended_gcd(a,m);(x%m+m)%m}pub fn comb(a: i64, b: i64, f: &Vec<(i64, i64)>)->i64{if a<b{return 0;}if b==0 || a==b{ return 1; }else{let x=f[a as usize].0;let y=f[(a-b) as usize].1;let z=f[b as usize].1;return((x*y)%MOD)*z%MOD;}}pub fn factorial(x: i64)->Vec<(i64, i64)>{let mut f=vec![(1i64,1i64),(1, 1)];let mut z = 1i64;let mut inv = vec![0; x as usize+10];inv[1] = 1;for i in 2..x+1{z=(z*i)%MOD;let w=(MOD-inv[(MOD%i)as usize]*(MOD/i)%MOD)%MOD;inv[i as usize] = w;f.push((z, (f[i as usize-1].1*w)%MOD));}return f;}pub fn fast_mod_pow(x: i64,p: usize, m: i64)->i64{let mut res=1;let mut t=x;let mut z=p;while z > 0{if z%2==1{res = (res*t)%m;}t = (t*t)%m;z /= 2; }res}//use proconio::fastout;//#[fastout]fn main(){input!{k: usize,query: [(i64, i64); k],}let mut ac = 0;let mut need = Vec::with_capacity(2*k);for &(u, v) in &query{ac += u*v;need.push((u, v));need.push((v, 1));}need.sort();let mut z = 1;let mut idx = 1;let mut ans = 1;for &(x, k) in &need{while idx <= x{z = (z*idx)%MOD;idx += 1;}ans = (ans*mod_inverse(fast_mod_pow(z, k as usize, MOD), MOD))%MOD;}for i in idx..=ac{z = (z*i)%MOD;}ans = (ans*z)%MOD;println!("{}", ans);}