結果
問題 | No.612 Move on grid |
ユーザー | akakimidori |
提出日時 | 2021-12-03 07:47:07 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 700 ms / 2,500 ms |
コード長 | 4,323 bytes |
コンパイル時間 | 4,407 ms |
コンパイル使用メモリ | 162,464 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-18 22:42:14 |
合計ジャッジ時間 | 9,200 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 24 ms
4,376 KB |
testcase_04 | AC | 34 ms
4,380 KB |
testcase_05 | AC | 698 ms
4,380 KB |
testcase_06 | AC | 700 ms
4,380 KB |
testcase_07 | AC | 17 ms
4,380 KB |
testcase_08 | AC | 699 ms
4,376 KB |
testcase_09 | AC | 305 ms
4,380 KB |
testcase_10 | AC | 217 ms
4,380 KB |
testcase_11 | AC | 54 ms
4,376 KB |
testcase_12 | AC | 384 ms
4,380 KB |
testcase_13 | AC | 119 ms
4,376 KB |
testcase_14 | AC | 528 ms
4,380 KB |
testcase_15 | AC | 62 ms
4,376 KB |
testcase_16 | AC | 619 ms
4,380 KB |
testcase_17 | AC | 62 ms
4,380 KB |
testcase_18 | AC | 491 ms
4,380 KB |
testcase_19 | AC | 133 ms
4,380 KB |
testcase_20 | AC | 191 ms
4,380 KB |
ソースコード
use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; } pub struct ConstantModulo<const M: u32>; impl<const M: u32> Modulo for ConstantModulo<{ M }> { fn modulo() -> u32 { M } } pub struct ModInt<T>(u32, PhantomData<T>); impl<T> Clone for ModInt<T> { fn clone(&self) -> Self { Self::new_unchecked(self.0) } } impl<T> Copy for ModInt<T> {} impl<T: Modulo> Add for ModInt<T> { type Output = ModInt<T>; fn add(self, rhs: Self) -> Self::Output { let mut v = self.0 + rhs.0; if v >= T::modulo() { v -= T::modulo(); } Self::new_unchecked(v) } } impl<T: Modulo> AddAssign for ModInt<T> { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl<T: Modulo> Sub for ModInt<T> { type Output = ModInt<T>; fn sub(self, rhs: Self) -> Self::Output { let mut v = self.0 - rhs.0; if self.0 < rhs.0 { v += T::modulo(); } Self::new_unchecked(v) } } impl<T: Modulo> SubAssign for ModInt<T> { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl<T: Modulo> Mul for ModInt<T> { type Output = ModInt<T>; fn mul(self, rhs: Self) -> Self::Output { let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64; Self::new_unchecked(v as u32) } } impl<T: Modulo> MulAssign for ModInt<T> { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl<T: Modulo> Neg for ModInt<T> { type Output = ModInt<T>; fn neg(self) -> Self::Output { if self.is_zero() { Self::zero() } else { Self::new_unchecked(T::modulo() - self.0) } } } impl<T> std::fmt::Display for ModInt<T> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl<T> std::fmt::Debug for ModInt<T> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl<T> Default for ModInt<T> { fn default() -> Self { Self::zero() } } impl<T: Modulo> std::str::FromStr for ModInt<T> { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result<Self, Self::Err> { let val = s.parse::<u32>()?; Ok(ModInt::new(val)) } } impl<T: Modulo> From<usize> for ModInt<T> { fn from(val: usize) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl<T: Modulo> From<u64> for ModInt<T> { fn from(val: u64) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl<T> ModInt<T> { pub fn new_unchecked(n: u32) -> Self { ModInt(n, PhantomData) } pub fn zero() -> Self { ModInt::new_unchecked(0) } pub fn one() -> Self { ModInt::new_unchecked(1) } pub fn is_zero(&self) -> bool { self.0 == 0 } } impl<T: Modulo> ModInt<T> { pub fn new(d: u32) -> Self { ModInt::new_unchecked(d % T::modulo()) } pub fn pow(&self, mut n: u64) -> Self { let mut t = Self::one(); let mut s = *self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } pub fn inv(&self) -> Self { assert!(!self.is_zero()); self.pow(T::modulo() as u64 - 2) } } type M = ModInt<ConstantModulo<1_000_000_007>>; fn read() -> (i32, i32, i32, i32, i32, i32) { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let a = s.trim().split_whitespace().flat_map(|s| s.parse()).collect::<Vec<_>>(); (a[0], a[1], a[2], a[3], a[4], a[5]) } fn main() { let (t, a, b, c, d, e) = read(); type Map = std::collections::HashMap<i32, M>; let mut dp = Map::new(); dp.insert(0, M::one()); for _ in 0..t { let mut next = Map::new(); for (x, w) in dp { for d in [a, -a, b, -b, c, -c].iter() { *next.entry(x + *d).or_default() += w; } } dp = next; } let ans = dp.into_iter().filter(|p| d <= p.0 && p.0 <= e).fold(M::zero(), |s, p| s + p.1); println!("{}", ans); }