Submission #3411336
Source Code Expand
/// Thank you tanakh!!!
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let mut s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
const MOD: usize = 998244353;
fn main() {
input!(n: usize, a: usize, b: usize, k: usize);
let mut candidates = vec![];
for x in 0..(n + 1) {
if a * x > k {
break;
}
let rest = k - a * x;
if rest % b != 0 {
continue;
}
let y = rest / b;
if y > n {
continue;
}
candidates.push((x, y));
}
let combination = Combination::new(n + 1, MOD);
let mut ans = 0;
for &(x, y) in candidates.iter() {
let x = combination.get(n, x);
let y = combination.get(n, y);
ans = (ans + (x * y) % MOD) % MOD;
}
println!("{}", ans);
}
pub struct Combination {
fact: Vec<usize>,
inv_fact: Vec<usize>,
modulo: usize,
}
impl Combination {
pub fn new(max: usize, modulo: usize) -> Combination {
let mut inv = vec![0; max + 1];
let mut fact = vec![0; max + 1];
let mut inv_fact = vec![0; max + 1];
inv[1] = 1;
for i in 2..(max + 1) {
inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
}
fact[0] = 1;
inv_fact[0] = 1;
for i in 0..max {
fact[i + 1] = fact[i] * (i + 1) % modulo;
}
for i in 0..max {
inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
}
Combination {
fact: fact,
inv_fact: inv_fact,
modulo: modulo,
}
}
pub fn get(&self, x: usize, y: usize) -> usize {
assert!(x >= y);
self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo
}
}
Submission Info
Submission Time
2018-10-15 10:28:09+0900
Task
B - RGB Coloring
User
kenkoooo
Language
Rust (1.15.1)
Score
700
Code Size
3021 Byte
Status
AC
Exec Time
31 ms
Memory
21752 KB
Compile Error
warning: variable does not need to be mutable, #[warn(unused_mut)] on by default
--> ./Main.rs:9:13
|
9 | let mut s = {
| ^^^^^
...
55 | input!(n: usize, a: usize, b: usize, k: usize);
| ----------------------------------------------- in this macro invocation
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
700 / 700
Status
Set Name
Test Cases
Sample
sample01.txt, sample02.txt, sample03.txt
All
sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, sample01.txt, sample02.txt, sample03.txt
Case Name
Status
Exec Time
Memory
in01.txt
AC
16 ms
16636 KB
in02.txt
AC
19 ms
16636 KB
in03.txt
AC
15 ms
16636 KB
in04.txt
AC
17 ms
16636 KB
in05.txt
AC
16 ms
16636 KB
in06.txt
AC
15 ms
16636 KB
in07.txt
AC
16 ms
16636 KB
in08.txt
AC
6 ms
6396 KB
in09.txt
AC
16 ms
16636 KB
in10.txt
AC
13 ms
10492 KB
in11.txt
AC
13 ms
10492 KB
in12.txt
AC
6 ms
6396 KB
in13.txt
AC
12 ms
10492 KB
in14.txt
AC
4 ms
4352 KB
in15.txt
AC
6 ms
6396 KB
in16.txt
AC
3 ms
4352 KB
in17.txt
AC
14 ms
10492 KB
in18.txt
AC
24 ms
18684 KB
in19.txt
AC
31 ms
21752 KB
in20.txt
AC
30 ms
21752 KB
in21.txt
AC
2 ms
4352 KB
sample01.txt
AC
2 ms
4352 KB
sample02.txt
AC
2 ms
4352 KB
sample03.txt
AC
6 ms
6396 KB