結果

問題 No.1304 あなたは基本が何か知っていますか?私は知っています.
ユーザー くれちー
提出日時 2020-12-01 01:59:21
言語 Rust
(1.83.0 + proconio)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 11,319 bytes
コンパイル時間 14,351 ms
コンパイル使用メモリ 388,784 KB
実行使用メモリ 684,980 KB
最終ジャッジ日時 2024-06-12 08:52:02
合計ジャッジ時間 79,857 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 36 TLE * 19 MLE * 19
権限があれば一括ダウンロードができます

ソースコード

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

// The main code is at the very bottom.
#[allow(unused_imports)]
use {
lib::byte::ByteChar,
std::cell::{Cell, RefCell},
std::cmp::{
self,
Ordering::{self, *},
Reverse,
},
std::collections::*,
std::convert::identity,
std::fmt::{self, Debug, Display, Formatter},
std::io::prelude::*,
std::iter::{self, FromIterator},
std::marker::PhantomData,
std::mem,
std::num::Wrapping,
std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive},
std::process,
std::rc::Rc,
std::thread,
std::time::{Duration, Instant},
std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize},
};
#[allow(unused_imports)]
#[macro_use]
pub mod lib {
pub mod byte {
pub use self::byte_char::*;
mod byte_char {
use std::error::Error;
use std::fmt::{self, Debug, Display, Formatter};
use std::str::FromStr;
#[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(transparent)]
pub struct ByteChar(pub u8);
impl Debug for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "b'{}'", self.0 as char)
}
}
impl Display for ByteChar {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{}", self.0 as char)
}
}
impl FromStr for ByteChar {
type Err = ParseByteCharError;
fn from_str(s: &str) -> Result<ByteChar, ParseByteCharError> {
match s.as_bytes().len() {
1 => Ok(ByteChar(s.as_bytes()[0])),
0 => Err(ParseByteCharErrorKind::EmptyStr.into()),
_ => Err(ParseByteCharErrorKind::TooManyBytes.into()),
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub struct ParseByteCharError {
kind: ParseByteCharErrorKind,
}
impl Display for ParseByteCharError {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
f.write_str(match self.kind {
ParseByteCharErrorKind::EmptyStr => "empty string",
ParseByteCharErrorKind::TooManyBytes => "too many bytes",
})
}
}
impl Error for ParseByteCharError {}
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
enum ParseByteCharErrorKind {
EmptyStr,
TooManyBytes,
}
impl From<ParseByteCharErrorKind> for ParseByteCharError {
fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError {
ParseByteCharError { kind }
}
}
}
}
pub mod io {
pub use self::scanner::*;
mod scanner {
use std::io::{self, BufRead};
use std::iter;
use std::str::FromStr;
#[derive(Debug)]
pub struct Scanner<R> {
reader: R,
buf: String,
pos: usize,
}
impl<R: BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Scanner {
reader,
buf: String::new(),
pos: 0,
}
}
pub fn next(&mut self) -> io::Result<&str> {
let start = loop {
match self.rest().find(|c| c != ' ') {
Some(i) => break i,
None => self.fill_buf()?,
}
};
self.pos += start;
let len = self.rest().find(' ').unwrap_or(self.rest().len());
let s = &self.buf[self.pos..][..len]; // self.rest()[..len]
self.pos += len;
Ok(s)
}
pub fn parse_next<T>(&mut self) -> io::Result<Result<T, T::Err>>
where
T: FromStr,
{
Ok(self.next()?.parse())
}
pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>
where
T: FromStr,
{
iter::repeat_with(|| self.parse_next()).take(n).collect()
}
pub fn map_next_bytes<T, F>(&mut self, mut f: F) -> io::Result<Vec<T>>
where
F: FnMut(u8) -> T,
{
Ok(self.next()?.bytes().map(&mut f).collect())
}
pub fn map_next_bytes_n<T, F>(&mut self, n: usize, mut f: F) -> io::Result<Vec<Vec<T>>>
where
F: FnMut(u8) -> T,
{
iter::repeat_with(|| self.map_next_bytes(&mut f))
.take(n)
.collect()
}
fn rest(&self) -> &str {
&self.buf[self.pos..]
}
fn fill_buf(&mut self) -> io::Result<()> {
self.buf.clear();
self.pos = 0;
let read = self.reader.read_line(&mut self.buf)?;
if read == 0 {
return Err(io::ErrorKind::UnexpectedEof.into());
}
if *self.buf.as_bytes().last().unwrap() == b'\n' {
self.buf.pop();
}
Ok(())
}
}
}
}
}
mod automaton_dp {
use std::{collections::HashMap, hash::Hash, mem};
pub trait Monoid {
fn op(&self, rhs: &Self) -> Self;
fn identity() -> Self;
}
impl<T0: Monoid, T1: Monoid> Monoid for (T0, T1) {
fn op(&self, rhs: &Self) -> Self {
(self.0.op(&rhs.0), self.1.op(&rhs.1))
}
fn identity() -> Self {
(T0::identity(), T1::identity())
}
}
pub trait Dfa {
type Char;
type State;
fn initial_state(&self) -> Option<Self::State>;
fn next_state(&self, state: &Self::State, c: &Self::Char) -> Option<Self::State>;
fn is_accept_state(&self, state: &Self::State) -> bool;
}
pub fn automaton_dp<A, M>(
dfa: A,
sigma: impl IntoIterator<Item = A::Char> + Clone,
len: usize,
mut mul: impl FnMut(&M, &A::Char) -> M,
e: M,
) -> M
where
A: Dfa,
A::State: Eq + Hash,
M: Monoid,
{
let mut dp = HashMap::<A::State, M>::new();
let mut dp_next = HashMap::<A::State, M>::new();
if let Some(initial_state) = dfa.initial_state() {
dp.insert(initial_state, e);
}
for _ in 0..len {
for (state, value) in dp.drain() {
for c in sigma.clone() {
if let Some(next_state) = dfa.next_state(&state, &c) {
let value = mul(&value, &c);
dp_next
.entry(next_state)
.and_modify(|acc| *acc = acc.op(&value))
.or_insert(value);
}
}
}
mem::swap(&mut dp, &mut dp_next);
dp_next.clear();
}
let mut acc = M::identity();
for (state, value) in dp {
if dfa.is_accept_state(&state) {
acc = acc.op(&value);
}
}
acc
}
pub struct And<A0, A1>(pub A0, pub A1);
impl<A0, A1> Dfa for And<A0, A1>
where
A0: Dfa,
A1: Dfa<Char = A0::Char>,
{
type Char = A0::Char;
type State = (A0::State, A1::State);
fn initial_state(&self) -> Option<Self::State> {
match (self.0.initial_state(), self.1.initial_state()) {
(Some(st0), Some(st1)) => Some((st0, st1)),
_ => None,
}
}
fn next_state(&self, state: &Self::State, c: &Self::Char) -> Option<Self::State> {
match (
self.0.next_state(&state.0, c),
self.1.next_state(&state.1, c),
) {
(Some(st0), Some(st1)) => Some((st0, st1)),
_ => None,
}
}
fn is_accept_state(&self, state: &Self::State) -> bool {
self.0.is_accept_state(&state.0) && self.1.is_accept_state(&state.1)
}
}
}
#[allow(unused_macros)]
macro_rules! eprint {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::eprint!($($arg)*)
}
};
}
#[allow(unused_macros)]
macro_rules! eprintln {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::eprintln!($($arg)*)
}
};
}
#[allow(unused_macros)]
macro_rules! dbg {
($($arg:tt)*) => {
if cfg!(debug_assertions) {
std::dbg!($($arg)*)
} else {
($($arg)*)
}
};
}
const CUSTOM_STACK_SIZE_MIB: Option<usize> = Some(1024);
const INTERACTIVE: bool = false;
fn main() -> std::io::Result<()> {
match CUSTOM_STACK_SIZE_MIB {
Some(stack_size_mib) => std::thread::Builder::new()
.name("run_solver".to_owned())
.stack_size(stack_size_mib * 1024 * 1024)
.spawn(run_solver)?
.join()
.unwrap(),
None => run_solver(),
}
}
fn run_solver() -> std::io::Result<()> {
let stdin = std::io::stdin();
let reader = stdin.lock();
let stdout = std::io::stdout();
let writer = stdout.lock();
macro_rules! with_wrapper {
($($wrapper:expr)?) => {{
let mut writer = $($wrapper)?(writer);
solve(reader, &mut writer)?;
writer.flush()
}};
}
if cfg!(debug_assertions) || INTERACTIVE {
with_wrapper!()
} else {
with_wrapper!(std::io::BufWriter::new)
}
}
fn solve<R, W>(reader: R, mut writer: W) -> std::io::Result<()>
where
R: BufRead,
W: Write,
{
let mut _scanner = lib::io::Scanner::new(reader);
#[allow(unused_macros)]
macro_rules! scan {
($T:ty) => {
_scanner.parse_next::<$T>()?.unwrap()
};
($($T:ty),+) => {
($(scan!($T)),+)
};
($T:ty; $n:expr) => {
_scanner.parse_next_n::<$T>($n)?.unwrap()
};
($($T:ty),+; $n:expr) => {
iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) })
.take($n)
.collect::<std::io::Result<Vec<_>>>()?
};
}
#[allow(unused_macros)]
macro_rules! scan_bytes_map {
($f:expr) => {
_scanner.map_next_bytes($f)?
};
($f:expr; $n:expr) => {
_scanner.map_next_bytes_n($n, $f)?
};
}
#[allow(unused_macros)]
macro_rules! print {
($($arg:tt)*) => {
write!(writer, $($arg)*)?
};
}
#[allow(unused_macros)]
macro_rules! println {
($($arg:tt)*) => {
writeln!(writer, $($arg)*)?
};
}
#[allow(unused_macros)]
macro_rules! answer {
($($arg:tt)*) => {{
println!($($arg)*);
return Ok(());
}};
}
{
use automaton_dp::*;
const MOD: u64 = 998244353;
#[derive(Clone, Copy)]
struct ModSum(u64);
impl Monoid for ModSum {
fn op(&self, rhs: &Self) -> Self {
let mut sum = self.0 + rhs.0;
if sum >= MOD {
sum -= MOD;
}
ModSum(sum)
}
fn identity() -> Self {
ModSum(0)
}
}
#[derive(Clone)]
struct GoodXor(RangeInclusive<u32>);
impl Dfa for GoodXor {
type Char = u32;
type State = u32;
fn initial_state(&self) -> Option<u32> {
Some(0)
}
fn next_state(&self, s: &u32, c: &u32) -> Option<u32> {
Some(s ^ c)
}
fn is_accept_state(&self, s: &u32) -> bool {
self.0.contains(s)
}
}
#[derive(Clone)]
struct LocallyDistinct;
impl Dfa for LocallyDistinct {
type Char = u32;
type State = Option<u32>;
fn initial_state(&self) -> Option<Option<u32>> {
Some(None)
}
fn next_state(&self, s: &Option<u32>, c: &u32) -> Option<Option<u32>> {
if *s != Some(*c) {
Some(Some(*c))
} else {
None
}
}
fn is_accept_state(&self, _: &Option<u32>) -> bool {
true
}
}
let (n, k, x, y) = scan!(usize, usize, u32, u32);
let a = scan!(u32; k);
let dfa = And(GoodXor(x..=y), LocallyDistinct);
let ans = automaton_dp(dfa, a.iter().copied(), n, |x, _| *x, ModSum(1));
println!("{}", ans.0);
}
#[allow(unreachable_code)]
Ok(())
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0