結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
![]() |
提出日時 | 2025-08-24 13:17:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 9,086 bytes |
コンパイル時間 | 11,095 ms |
コンパイル使用メモリ | 403,628 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-24 13:17:22 |
合計ジャッジ時間 | 12,216 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
use modint::ModInt998244353; use proconio::input; use std::io::Write; type Mint = ModInt998244353; const ELEMENTS: [i32; 4] = [1, 2, -1, -2]; const STATES: [i32; 7] = [1, -1, 2, -2, 4, -4, -8]; const K: usize = STATES.len(); type Mat = [[Mint; K]; K]; fn main() { input! { t: usize } let mut writer = std::io::BufWriter::new(std::io::stdout().lock()); for _ in 0..t { input! { n: usize } let ans = solve(n); writeln!(writer, "{ans}").unwrap(); } } fn solve(n: usize) -> Mint { let mut transition = [[Mint::new(0); K]; K]; for (i, &state) in STATES.iter().enumerate() { for &e in &ELEMENTS { let nstate = state * e; if nstate.abs() > 8 { continue; } let j = STATES.iter().position(|&x| x == nstate).unwrap_or(0); transition[i][j] += 1; } } let acc = pow(&transition, n); let ans = acc[0][0] - Mint::new(2).pow(n as u64 - 1); ans } fn mul(a: &Mat, b: &Mat) -> Mat { let mut res = [[Mint::new(0); K]; K]; for i in 0..K { for j in 0..K { for k in 0..K { res[i][j] += a[i][k] * b[k][j]; } } } res } fn pow(a: &Mat, mut k: usize) -> Mat { assert!(k > 0); k -= 1; let mut res = a.clone(); let mut pow = a.clone(); while k > 0 { if k & 1 == 1 { res = mul(&res, &pow); } pow = mul(&pow, &pow); k >>= 1; } res } // f(3) = C(3, 3) * (C(3, 0) + C(3, 2)) = 1 * 4 = 4 // f(4) = C(4, 3) * (C(4, 0) + C(4, 2) + C(4, 4)) = 4 * 8 = 32 // f(5) = C(5, 3) * (C(5, 0) + C(5, 2) + C(5, 4)) = 10 * 16 = 160 // f(6) = C(6, 3) * (C(6, 0) + C(6, 2) + C(6, 4) + C(6, 6)) + 2 * f(3) = 20 * 32 + 2 * 4 = 648 #[allow(dead_code)] mod modint { use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign}; pub type ModInt998244353 = ModInt<998244353>; pub type ModInt1000000007 = ModInt<1000000007>; type ModIntInner = u64; #[derive(Clone, Copy, PartialEq, Eq)] pub struct ModInt<const M: ModIntInner> { val: ModIntInner, } impl<const M: ModIntInner> ModInt<M> { const IS_PRIME: bool = is_prime(M as u32); pub const fn modulus() -> ModIntInner { M } pub const fn new(val: ModIntInner) -> Self { assert!(M < (1 << 31)); Self { val: val.rem_euclid(M), } } pub const fn new_unchecked(val: ModIntInner) -> Self { Self { val } } pub const fn val(&self) -> ModIntInner { self.val } pub fn pow(self, mut exp: u64) -> Self { let mut result = Self::new(1); let mut base = self; while exp > 0 { if exp & 1 == 1 { result *= base; } base *= base; exp >>= 1; } result } pub fn inv(self) -> Self { assert!(Self::IS_PRIME); self.pow(M as u64 - 2).into() } } impl<const M: ModIntInner> std::fmt::Display for ModInt<M> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.val) } } impl<const M: ModIntInner> std::fmt::Debug for ModInt<M> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.val) } } impl<const M: ModIntInner> std::str::FromStr for ModInt<M> { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result<Self, Self::Err> { let value = s.parse::<ModIntInner>()?; Ok(ModInt::new(value)) } } impl<const M: ModIntInner> Neg for ModInt<M> { type Output = Self; fn neg(mut self) -> Self::Output { if self.val > 0 { self.val = M - self.val; } self } } impl<const M: ModIntInner, T: Into<ModInt<M>>> AddAssign<T> for ModInt<M> { fn add_assign(&mut self, rhs: T) { self.val += rhs.into().val; if self.val >= M { self.val -= M; } } } impl<const M: ModIntInner, T: Into<ModInt<M>>> SubAssign<T> for ModInt<M> { fn sub_assign(&mut self, rhs: T) { self.val = self.val.wrapping_sub(rhs.into().val); if self.val > M { self.val = self.val.wrapping_add(M); } } } impl<const M: ModIntInner, T: Into<ModInt<M>>> MulAssign<T> for ModInt<M> { fn mul_assign(&mut self, rhs: T) { self.val = self.val * rhs.into().val % M; } } impl<const M: ModIntInner, T: Into<ModInt<M>>> DivAssign<T> for ModInt<M> { fn div_assign(&mut self, rhs: T) { *self *= rhs.into().inv(); } } macro_rules! impl_binnary_operators { ($({ $op: ident, $op_assign: ident, $fn: ident, $fn_assign: ident}),*) => {$( impl<const M: ModIntInner, T: Into<ModInt<M>>> $op<T> for ModInt<M> { type Output = ModInt<M>; fn $fn(mut self, rhs: T) -> ModInt<M> { self.$fn_assign(rhs.into()); self } } impl<const M: ModIntInner> $op<&ModInt<M>> for ModInt<M> { type Output = ModInt<M>; fn $fn(self, rhs: &ModInt<M>) -> ModInt<M> { self.$fn(*rhs) } } impl<const M: ModIntInner, T: Into<ModInt<M>>> $op<T> for &ModInt<M> { type Output = ModInt<M>; fn $fn(self, rhs: T) -> ModInt<M> { (*self).$fn(rhs.into()) } } impl<const M: ModIntInner> $op<&ModInt<M>> for &ModInt<M> { type Output = ModInt<M>; fn $fn(self, rhs: &ModInt<M>) -> ModInt<M> { (*self).$fn(*rhs) } } impl<const M: ModIntInner> $op_assign<&ModInt<M>> for ModInt<M> { fn $fn_assign(&mut self, rhs: &ModInt<M>) { *self = self.$fn(*rhs); } } )*}; } impl_binnary_operators!( {Add, AddAssign, add, add_assign}, {Sub, SubAssign, sub, sub_assign}, {Mul, MulAssign, mul, mul_assign}, {Div, DivAssign, div, div_assign} ); impl<const M: ModIntInner> std::iter::Sum for ModInt<M> { fn sum<I: Iterator<Item = Self>>(iter: I) -> Self { iter.fold(Self::new(0), Add::add) } } impl<'a, const M: ModIntInner> std::iter::Sum<&'a Self> for ModInt<M> { fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self { iter.fold(Self::new(0), Add::add) } } impl<const M: ModIntInner> std::iter::Product for ModInt<M> { fn product<I: Iterator<Item = Self>>(iter: I) -> Self { iter.fold(Self::new(1), Mul::mul) } } impl<'a, const M: ModIntInner> std::iter::Product<&'a Self> for ModInt<M> { fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self { iter.fold(Self::new(1), Mul::mul) } } macro_rules! impl_rem_euclid_signed { ($($ty:tt),*) => { $( impl<const M: ModIntInner> From<$ty> for ModInt<M> { fn from(value: $ty) -> ModInt<M> { Self::new_unchecked((value as i64).rem_euclid(M as i64) as ModIntInner) } } )* }; } impl_rem_euclid_signed!(i8, i16, i32, i64, isize); macro_rules! impl_rem_euclid_unsigned { ($($ty:tt),*) => { $( impl<const M: ModIntInner> From<$ty> for ModInt<M> { fn from(value: $ty) -> ModInt<M> { Self::new_unchecked((value as u64).rem_euclid(M as u64) as ModIntInner) } } )* }; } impl_rem_euclid_unsigned!(u8, u16, u32, u64, usize); const fn is_prime(n: u32) -> bool { const fn miller_rabin(n: u32, witness: u32) -> bool { let (n, witness) = (n as u64, witness as u64); let mut d = n >> (n - 1).trailing_zeros(); let mut y = { let (mut res, mut pow, mut e) = (1, witness, d); while e > 0 { if e & 1 == 1 { res = res * pow % n; } pow = pow * pow % n; e >>= 1; } res }; while d != n - 1 && y != 1 && y != n - 1 { y = y * y % n; d <<= 1; } y == n - 1 || d & 1 == 1 } const WITNESS: [u32; 3] = [2, 7, 61]; if n == 1 || n % 2 == 0 { return n == 2; } let mut i = 0; while i < WITNESS.len() { if !miller_rabin(n, WITNESS[i]) { return false; } i += 1; } true } }