結果

問題 No.1476 esreveR dna esreveR
ユーザー RheoTommy
提出日時 2021-04-16 20:30:34
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 9,153 bytes
コンパイル時間 14,933 ms
コンパイル使用メモリ 379,516 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-02 22:49:19
合計ジャッジ時間 15,837 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

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

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]
// #
// - use
// - lib
// - main
// - basic
//
// 使 basic
// 使 lib
// → https://github.com/RheoTommy/at_coder
// Twitter → https://twitter.com/RheoTommy
use std::collections::*;
use std::io::{stdout, BufWriter, Write};
use crate::basic::*;
use crate::lib::*;
pub mod lib {
pub type ModInt = StaticModInt;
pub const MOD: i32 = MOD998244353;
pub const MOD1000000007: i32 = 1000000007;
pub const MOD998244353: i32 = 998244353;
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
pub struct StaticModInt(i32);
impl std::fmt::Display for StaticModInt {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
impl std::fmt::Debug for StaticModInt {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self)
}
}
impl StaticModInt {
pub fn new<T: Into<StaticModInt>>(n: T) -> Self {
n.into()
}
fn new_inner(n: i32) -> Self {
Self(n)
}
pub fn pow<T: Into<Int>>(self, n: T) -> Self {
let n: Int = n.into();
let mut n = n.0;
assert!(n >= 0);
let mut res = StaticModInt::new(1);
let mut x = self;
while n != 0 {
if n & 1 == 1 {
res *= x;
}
n /= 2;
x *= x;
}
res
}
pub fn inv(self) -> Self {
self.pow((MOD - 2) as u64)
}
}
impl<T: Into<Int>> From<T> for StaticModInt {
fn from(t: T) -> Self {
let n: Int = t.into();
let n = (n.0 % MOD as i64) as i32;
if n < 0 {
Self::new_inner(n + MOD)
} else {
Self::new_inner(n)
}
}
}
impl<T: Into<StaticModInt>> std::ops::Add<T> for StaticModInt {
type Output = Self;
fn add(self, rhs: T) -> Self::Output {
let mut tmp = self.0;
let t: StaticModInt = rhs.into();
tmp += t.0;
if tmp >= MOD {
tmp -= MOD;
}
debug_assert!((0..MOD).contains(&tmp));
Self(tmp)
}
}
impl<T: Into<StaticModInt>> std::ops::AddAssign<T> for StaticModInt {
fn add_assign(&mut self, rhs: T) {
*self = *self + rhs.into()
}
}
impl<T: Into<StaticModInt>> std::ops::Sub<T> for StaticModInt {
type Output = Self;
fn sub(self, rhs: T) -> Self::Output {
let mut tmp = self.0;
let t: StaticModInt = rhs.into();
tmp -= t.0;
if tmp < 0 {
tmp += MOD;
}
debug_assert!((0..MOD).contains(&tmp));
Self(tmp)
}
}
impl<T: Into<StaticModInt>> std::ops::SubAssign<T> for StaticModInt {
fn sub_assign(&mut self, rhs: T) {
*self = *self - rhs.into();
}
}
impl<T: Into<StaticModInt>> std::ops::Mul<T> for StaticModInt {
type Output = Self;
fn mul(self, rhs: T) -> Self::Output {
let mut tmp = self.0 as i64;
let t: StaticModInt = rhs.into();
tmp *= t.0 as i64;
if tmp >= MOD as i64 {
tmp %= MOD as i64;
}
let tmp = tmp as i32;
debug_assert!((0..MOD).contains(&tmp));
Self(tmp)
}
}
impl<T: Into<StaticModInt>> std::ops::MulAssign<T> for StaticModInt {
fn mul_assign(&mut self, rhs: T) {
*self = *self * rhs.into();
}
}
impl<T: Into<StaticModInt>> std::ops::Div<T> for StaticModInt {
type Output = Self;
fn div(self, rhs: T) -> Self::Output {
let t: StaticModInt = rhs.into();
self * t.inv()
}
}
impl<T: Into<StaticModInt>> std::ops::DivAssign<T> for StaticModInt {
fn div_assign(&mut self, rhs: T) {
*self = *self / rhs.into();
}
}
///
/// O(N)
/// O(1)
/// O(N)
pub struct CombTable {
fac: Vec<ModInt>,
f_inv: Vec<ModInt>,
}
impl CombTable {
/// O(N)
pub fn new<T: Into<Int>>(n: T) -> Self {
let n: Int = n.into();
assert!(n.0 >= 0);
let n = n.0 as usize;
let mut fac = vec![ModInt::new(1); n + 1];
let mut f_inv = vec![ModInt::new(1); n + 1];
let mut inv = vec![ModInt::new(1); n + 1];
inv[0] = ModInt::new(0);
for i in 2..=n {
fac[i] = fac[i - 1] * i;
inv[i] =
ModInt::new(MOD) - inv[(MOD % i as i32) as usize] * ModInt::new(MOD / i as i32);
f_inv[i] = f_inv[i - 1] * inv[i];
}
Self { fac, f_inv }
}
/// nCkO(1)
pub fn comb<T1: Into<Int>, T2: Into<Int>>(&self, n: T1, k: T2) -> ModInt {
let n: Int = n.into();
let k: Int = k.into();
assert!(n.0 >= 0);
assert!(k.0 >= 0);
let n = n.0 as usize;
let k = k.0 as usize;
if n < k {
return ModInt::new(0);
}
self.fac[n] * (self.f_inv[k] * self.f_inv[n - k])
}
}
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug)]
pub struct Int(pub i64);
macro_rules! impl_int_from {($ ($ t : ty ) ,* ) => {$ (impl From < Int > for $ t {fn from (t : Int ) -> $ t {t . 0 as $ t } } ) * } ; }
impl_int_from!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
macro_rules! impl_int_into {($ ($ t : ty ) ,* ) => {$ (impl Into < Int > for $ t {fn into (self ) -> Int {Int (self as i64 ) } } ) * } ; }
impl_int_into!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
}
fn main() {
let mut io = IO::new();
let n = io.next_usize();
let c = CombTable::new(5);
let c = c.comb(4, 2);
let res = c.pow(n / 2);
io.println(res);
}
pub mod basic {
pub const U_INF: u64 = (1 << 60) + (1 << 30);
pub const I_INF: i64 = (1 << 60) + (1 << 30);
pub struct IO {
iter: std::str::SplitAsciiWhitespace<'static>,
buf: std::io::BufWriter<std::io::StdoutLock<'static>>,
}
impl Default for IO {
fn default() -> Self {
Self::new()
}
}
impl IO {
pub fn new() -> Self {
use std::io::*;
let mut input = String::new();
std::io::stdin().read_to_string(&mut input).unwrap();
let input = Box::leak(input.into_boxed_str());
let out = Box::new(stdout());
IO {
iter: input.split_ascii_whitespace(),
buf: BufWriter::new(Box::leak(out).lock()),
}
}
pub fn next_str(&mut self) -> &str {
self.iter.next().unwrap()
}
pub fn read<T: std::str::FromStr>(&mut self) -> T
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
{
self.iter.next().unwrap().parse().unwrap()
}
pub fn next_usize(&mut self) -> usize {
self.read()
}
pub fn next_uint(&mut self) -> u64 {
self.read()
}
pub fn next_int(&mut self) -> i64 {
self.read()
}
pub fn next_float(&mut self) -> f64 {
self.read()
}
pub fn next_chars(&mut self) -> std::str::Chars {
self.next_str().chars()
}
pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
{
(0..n).map(|_| self.read()).collect::<Vec<_>>()
}
pub fn print<T: std::fmt::Display>(&mut self, t: T) {
use std::io::Write;
write!(self.buf, "{}", t).unwrap();
}
pub fn println<T: std::fmt::Display>(&mut self, t: T) {
self.print(t);
self.print("\n");
}
pub fn print_iter<T: std::fmt::Display, I: Iterator<Item=T>>(
&mut self,
mut iter: I,
sep: &str,
) {
if let Some(v) = iter.next() {
self.print(v);
for vi in iter {
self.print(sep);
self.print(vi);
}
}
self.print("\n");
}
pub fn flush(&mut self) {
use std::io::Write;
self.buf.flush().unwrap();
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0