結果

問題 No.2527 H and W
ユーザー ikoma
提出日時 2023-11-03 23:37:35
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 3,768 bytes
コンパイル時間 14,817 ms
コンパイル使用メモリ 386,740 KB
実行使用メモリ 17,664 KB
最終ジャッジ日時 2024-09-25 21:34:29
合計ジャッジ時間 15,515 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![allow(unused_imports, dead_code, unused_macros, unused_variables, non_snake_case, unused_parens)]
use std::cmp::{min,max,Ordering,Reverse};
use std::mem::swap;
use std::collections::{VecDeque,LinkedList,HashMap,BTreeMap,HashSet,BTreeSet,BinaryHeap};
fn solve() {
input! {
h: usize,
w: usize,
k: usize,
}
let cmb = ModCombination::new(h.max(w));
let mut ans = 0;
for i in 1..=h {
if k % i != 0 {continue}
let j = k / i;
// if j == w{continue}
ans = (ans + cmb.nCr(h, i) * cmb.nCr(w, j)) % MOD;
}
// if k % w == 0 {
// let x = k / w;
// ans = (ans + cmb.nCr(h, x)) % MOD;
// }
// if k % h == 0 {
// let x = k / h;
// ans = (ans + cmb.nCr(w, x)) % MOD;
// }
println!("{}", ans);
}
fn main() {
std::thread::Builder::new()
.stack_size(128 * 1024 * 1024)
.spawn(|| solve()).unwrap()
.join().unwrap();
}
type Int = i64;
const MOD:Int = 998244353;
const fn pow_mod(x: Int, mut n: Int, m: Int) -> Int {
if m == 1 {
return 0;
}
let mut r: u64 = 1;
let mut y: u64 = x.rem_euclid(m) as u64;
while n != 0 {
if (n & 1) > 0 {
r = (r * y) % (m as u64);
}
y = (y * y) % (m as u64);
n >>= 1;
}
r as Int
}
pub struct ModCombination {
fac: Vec<Int>,
ifac: Vec<Int>,
}
impl ModCombination {
pub fn new(size:usize) -> Self {
let mut fac = vec![1; size+1];
let mut f = 1;
let mut i = 2;
while i <= size {
f = f * i as Int % MOD;
fac[i] = f;
i+=1;
}
let mut ifac = vec![1; size+1];
let mut f = pow_mod(fac[size], MOD-2, MOD);
ifac[size] = f;
let mut i = size;
while i > 0 {
f = f * i as Int % MOD;
i-=1;
ifac[i] = f;
}
Self {fac, ifac}
}
#[inline]
pub fn nCr(&self, n:usize, r:usize) -> Int {
if n < r {
return 0;
}
self.fac[n] * self.ifac[r] % MOD * self.ifac[n-r] % MOD
}
#[inline]
pub fn nPr(&self, n:usize, r:usize) -> Int {
if n < r {
return 0;
}
self.fac[n] * self.ifac[n-r] % MOD
}
#[inline]
pub fn nHr(&self, n:usize, r:usize) -> Int {
if n==0 && r==0 {return 1;}
self.nCr(n+r-1, r)
}
}
mod _input {
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($next:expr) => {};
($next:expr, ) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => {
( $(read_value!($next, $t)),* )
};
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, usize1) => {
read_value!($next, usize) - 1
};
($next:expr, $t:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0