結果
問題 | No.1310 量子アニーリング |
ユーザー |
|
提出日時 | 2020-12-15 16:31:30 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 7,094 bytes |
コンパイル時間 | 15,400 ms |
コンパイル使用メモリ | 377,736 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 01:45:29 |
合計ジャッジ時間 | 12,338 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#![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),*) }}// @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);}}#[macro_export]macro_rules! mint {($x:expr) => {ModInt::new($x, MOD_998244353)};}fn main() {let mut sc = Scanner::new();let n: i64 = sc.cin();// Binom(n; k)let mut comb = mint!(1);let mut ans = mint!(0);for k in 0..=n {if k % 2 == 0 {let pow = mint!(2).pow((n - 2 * k).abs());// trace!(comb, pow);ans += comb * pow;}comb = comb * (n - k) / (k + 1);}put!(2 * ans);}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()}}