結果
問題 | No.1476 esreveR dna esreveR |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#![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/RheoTommyuse 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 }}/// nCkをO(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) -> Twhere<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();}}}