結果
問題 | No.1304 あなたは基本が何か知っていますか?私は知っています. |
ユーザー | cympfh |
提出日時 | 2020-12-01 14:15:58 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 407 ms / 2,000 ms |
コード長 | 8,013 bytes |
コンパイル時間 | 5,718 ms |
コンパイル使用メモリ | 168,828 KB |
実行使用メモリ | 495,096 KB |
最終ジャッジ日時 | 2023-09-03 03:27:19 |
合計ジャッジ時間 | 13,551 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
34,888 KB |
testcase_01 | AC | 55 ms
67,768 KB |
testcase_02 | AC | 27 ms
34,920 KB |
testcase_03 | AC | 407 ms
495,096 KB |
testcase_04 | AC | 68 ms
34,968 KB |
testcase_05 | AC | 49 ms
34,688 KB |
testcase_06 | AC | 26 ms
34,816 KB |
testcase_07 | AC | 62 ms
34,868 KB |
testcase_08 | AC | 84 ms
100,376 KB |
testcase_09 | AC | 60 ms
34,852 KB |
testcase_10 | AC | 55 ms
34,916 KB |
testcase_11 | AC | 62 ms
34,916 KB |
testcase_12 | AC | 55 ms
34,904 KB |
testcase_13 | AC | 46 ms
34,640 KB |
testcase_14 | AC | 51 ms
34,928 KB |
testcase_15 | AC | 50 ms
34,952 KB |
testcase_16 | AC | 52 ms
34,928 KB |
testcase_17 | AC | 62 ms
67,660 KB |
testcase_18 | AC | 52 ms
34,848 KB |
testcase_19 | AC | 41 ms
34,848 KB |
testcase_20 | AC | 28 ms
34,876 KB |
testcase_21 | AC | 70 ms
67,672 KB |
testcase_22 | AC | 54 ms
34,852 KB |
testcase_23 | AC | 61 ms
34,956 KB |
testcase_24 | AC | 69 ms
34,852 KB |
testcase_25 | AC | 155 ms
199,292 KB |
testcase_26 | AC | 81 ms
100,392 KB |
testcase_27 | AC | 86 ms
100,632 KB |
testcase_28 | AC | 108 ms
133,540 KB |
testcase_29 | AC | 82 ms
100,668 KB |
testcase_30 | AC | 127 ms
166,396 KB |
testcase_31 | AC | 209 ms
264,948 KB |
testcase_32 | AC | 86 ms
100,632 KB |
testcase_33 | AC | 155 ms
199,216 KB |
testcase_34 | AC | 84 ms
100,652 KB |
testcase_35 | AC | 132 ms
166,456 KB |
testcase_36 | AC | 183 ms
232,108 KB |
testcase_37 | AC | 132 ms
166,380 KB |
testcase_38 | AC | 130 ms
166,388 KB |
testcase_39 | AC | 229 ms
297,864 KB |
testcase_40 | AC | 129 ms
166,340 KB |
testcase_41 | AC | 227 ms
297,852 KB |
testcase_42 | AC | 130 ms
166,428 KB |
testcase_43 | AC | 130 ms
166,392 KB |
testcase_44 | AC | 182 ms
232,128 KB |
04_evil_A_01 | WA | - |
04_evil_A_02 | WA | - |
04_evil_A_03 | WA | - |
04_evil_A_04 | WA | - |
04_evil_A_05 | WA | - |
04_evil_A_06 | RE | - |
04_evil_A_07 | WA | - |
04_evil_A_08 | WA | - |
04_evil_A_09 | WA | - |
04_evil_A_10 | WA | - |
05_evil_B_01 | WA | - |
05_evil_B_02 | WA | - |
05_evil_B_03 | WA | - |
05_evil_B_04 | WA | - |
05_evil_B_05 | WA | - |
05_evil_B_06 | WA | - |
05_evil_B_07 | WA | - |
05_evil_B_08 | WA | - |
05_evil_B_09 | WA | - |
05_evil_B_10 | WA | - |
06_evil_C_01 | WA | - |
06_evil_C_02 | WA | - |
06_evil_C_03 | WA | - |
06_evil_C_04 | WA | - |
06_evil_C_05 | WA | - |
06_evil_C_06 | WA | - |
06_evil_C_07 | WA | - |
06_evil_C_08 | WA | - |
06_evil_C_09 | WA | - |
06_evil_C_10 | AC | 13 ms
18,296 KB |
ソースコード
#![allow(unused_imports, unused_macros, dead_code)] macro_rules! min { (.. $x:expr) => {{ let mut it = $x.iter(); it.next().map(|z| it.fold(z, |x, y| min!(x, y))) }}; ($x:expr) => ($x); ($x:expr, $($ys:expr),*) => {{ let t = min!($($ys),*); if $x < t { $x } else { t } }} } macro_rules! max { (.. $x:expr) => {{ let mut it = $x.iter(); it.next().map(|z| it.fold(z, |x, y| max!(x, y))) }}; ($x:expr) => ($x); ($x:expr, $($ys:expr),*) => {{ let t = max!($($ys),*); if $x > t { $x } else { t } }} } macro_rules! trace { ($x:expr) => { #[cfg(debug_assertions)] eprintln!(">>> {} = {:?}", stringify!($x), $x) }; ($($xs:expr),*) => { trace!(($($xs),*)) } } macro_rules! flush { () => { std::io::stdout().flush().unwrap(); }; } macro_rules! put { (.. $x:expr) => {{ let mut it = $x.iter(); if let Some(x) = it.next() { print!("{}", x); } for x in it { print!(" {}", x); } println!(""); }}; ($x:expr) => { println!("{}", $x) }; ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) } } macro_rules! mint { ($x:expr) => { ModInt::new($x, MOD_998244353) }; } fn main() { let mut sc = Scanner::new(); let n: usize = sc.cin(); let k: usize = sc.cin(); let x: usize = sc.cin(); let y: usize = sc.cin(); let xs: Vec<usize> = sc.vec(k); if x >= 1024 { put!(0); return; } let y = min!(y + 1, 1024); let required = x..y; let xs = dup(xs); // dp[i][z][x] = (長さ i の配列, 要素の xor が z, 最後の要素が x) let mut dp = vec![vec![vec![mint!(0); 1024]; 1024]; n]; // dp_sum[i][z] = (長さ i の配列, 要素の xor が z) let mut dp_sum = vec![vec![mint!(0); 1024]; n]; // 初期化 for &x in &xs { dp[0][x][x] = mint!(1); dp_sum[0][x] = mint!(1); } // 更新 for i in 1..n { for &x in &xs { // z: (i-1) までの総xor和 for z in 0..1024 { let a = dp_sum[i - 1][z] - dp[i - 1][z][x]; dp[i][z ^ x][x] += a; dp_sum[i][z ^ x] += a; } } } let mut ans = mint!(0); for z in required { ans += dp_sum[n - 1][z]; } put!(ans); } /// 重複排除 fn dup(xs: Vec<usize>) -> Vec<usize> { use std::collections::BTreeSet; xs.iter() .cloned() .collect::<BTreeSet<_>>() .iter() .cloned() .collect() } // @algebra/modint #[derive(Debug, PartialEq, Eq, Clone, Copy)] pub struct ModInt(pub i64, pub i64); // (residual, modulo) pub const MOD_1000000007: i64 = 1_000_000_007; pub const MOD_998244353: i64 = 998_244_353; impl ModInt { pub fn new(residual: i64, modulo: i64) -> ModInt { if residual >= modulo { ModInt(residual % modulo, modulo) } else if residual < 0 { ModInt((residual % modulo) + modulo, modulo) } else { ModInt(residual, modulo) } } pub fn unwrap(self) -> i64 { self.0 } pub fn inv(self) -> Self { fn exgcd(r0: i64, a0: i64, b0: i64, r: i64, a: i64, b: i64) -> (i64, i64, i64) { if r > 0 { exgcd(r, a, b, r0 % r, a0 - r0 / r * a, b0 - r0 / r * b) } else { (a0, b0, r0) } } let (a, _, r) = exgcd(self.0, 1, 0, self.1, 0, 1); if r != 1 { panic!("{:?} has no inverse!", self); } ModInt(((a % self.1) + self.1) % self.1, self.1) } pub fn pow(self, n: i64) -> Self { if n < 0 { self.pow(-n).inv() } else if n == 0 { ModInt(1, self.1) } else if n == 1 { self } else { let mut x = (self * self).pow(n / 2); if n % 2 == 1 { x *= self } x } } } impl std::fmt::Display for ModInt { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::ops::Neg for ModInt { type Output = Self; fn neg(self) -> Self { if self.0 == 0 { return self; } ModInt(self.1 - self.0, self.1) } } impl std::ops::Add<i64> for ModInt { type Output = Self; fn add(self, other: i64) -> Self { ModInt::new(self.0 + other, self.1) } } impl std::ops::Add for ModInt { type Output = Self; fn add(self, other: ModInt) -> Self { self + other.0 } } impl std::ops::Add<ModInt> for i64 { type Output = ModInt; fn add(self, other: ModInt) -> ModInt { other + self } } impl std::ops::AddAssign<i64> for ModInt { fn add_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 + other, self.1).0; } } impl std::ops::AddAssign for ModInt { fn add_assign(&mut self, other: ModInt) { *self += other.0; } } impl std::ops::Sub<i64> for ModInt { type Output = Self; fn sub(self, other: i64) -> Self { ModInt::new(self.0 - other, self.1) } } impl std::ops::Sub for ModInt { type Output = Self; fn sub(self, other: ModInt) -> Self { self - other.0 } } impl std::ops::Sub<ModInt> for i64 { type Output = ModInt; fn sub(self, other: ModInt) -> ModInt { ModInt::new(self - other.0, other.1) } } impl std::ops::SubAssign<i64> for ModInt { fn sub_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 - other, self.1).0; } } impl std::ops::SubAssign for ModInt { fn sub_assign(&mut self, other: ModInt) { *self -= other.0; } } impl std::ops::Mul<i64> for ModInt { type Output = Self; fn mul(self, other: i64) -> Self { ModInt::new(self.0 * other, self.1) } } impl std::ops::Mul for ModInt { type Output = Self; fn mul(self, other: ModInt) -> Self { self * other.0 } } impl std::ops::Mul<ModInt> for i64 { type Output = ModInt; fn mul(self, other: ModInt) -> ModInt { other * self } } impl std::ops::MulAssign<i64> for ModInt { fn mul_assign(&mut self, other: i64) { self.0 = ModInt::new(self.0 * other, self.1).0; } } impl std::ops::MulAssign for ModInt { fn mul_assign(&mut self, other: ModInt) { *self *= other.0; } } impl std::ops::Div for ModInt { type Output = Self; fn div(self, other: ModInt) -> Self { self * other.inv() } } impl std::ops::Div<i64> for ModInt { type Output = Self; fn div(self, other: i64) -> Self { self / ModInt::new(other, self.1) } } impl std::ops::Div<ModInt> for i64 { type Output = ModInt; fn div(self, other: ModInt) -> ModInt { other.inv() * self } } impl std::ops::DivAssign for ModInt { fn div_assign(&mut self, other: ModInt) { self.0 = (self.clone() / other).0; } } impl std::ops::DivAssign<i64> for ModInt { fn div_assign(&mut self, other: i64) { *self /= ModInt(other, self.1); } } use std::collections::VecDeque; use std::io::{self, Write}; use std::str::FromStr; struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, } impl Scanner { fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new(), } } fn cin<T: FromStr>(&mut self) -> T { while self.buffer.is_empty() { let mut line = String::new(); let _ = self.stdin.read_line(&mut line); for w in line.split_whitespace() { self.buffer.push_back(String::from(w)); } } self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap() } fn chars(&mut self) -> Vec<char> { self.cin::<String>().chars().collect() } fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.cin()).collect() } }