結果
| 問題 | No.1448 和差算 |
| ユーザー |
 RheoTommy
|
| 提出日時 | 2021-03-31 20:26:18 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 10,239 bytes |
| コンパイル時間 | 13,098 ms |
| コンパイル使用メモリ | 384,252 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-12-15 07:50:58 |
| 合計ジャッジ時間 | 12,756 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#![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 const MOD: i32 = MOD1000000007;pub const MOD1000000007: i32 = 1000000007;pub const MOD998244353: i32 = 998244353;/// 常に設定したModを取り続ける正整数型#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]pub struct ModInt {/// 保持する値value: i32,}impl ModInt {pub fn new<T: Into<ModInt>>(n: T) -> Self {n.into()}/// isizeを受け取り、ModIntに変換するfn new_inner(n: i32) -> Self {let mut value = n % MOD;if value < 0 {value += MOD;}Self { value }}/// べき乗計算関数/// 二分累乗法を用いるため、計算量はO(log n)pub fn pow(self, n: u64) -> Self {match n {0 => ModInt::new_inner(1),1 => self,n if n % 2 == 0 => (self * self).pow(n / 2),_ => self * self.pow(n - 1),}}/// 逆元を返す/// フェルマーの小定理より、べき乗を用いて計算するため、計算量はO(log MOD)pub fn inv(self) -> Self {self.pow((MOD - 2) as u64)}}impl std::fmt::Display for ModInt {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {write!(f, "{}", self.value)}}impl<T: Into<Num>> From<T> for ModInt {fn from(t: T) -> Self {let n: Num = t.into();Self::new_inner((n.0 % MOD as i64) as i32)}}impl<T: Into<ModInt>> std::ops::Add<T> for ModInt {type Output = ModInt;fn add(self, rhs: T) -> Self::Output {let mut tmp = self.value;let t: ModInt = rhs.into();tmp += t.value;if tmp >= MOD {tmp -= MOD;}Self { value: tmp }}}impl<T: Into<ModInt>> std::ops::AddAssign<T> for ModInt {fn add_assign(&mut self, rhs: T) {*self = *self + rhs.into()}}impl<T: Into<ModInt>> std::ops::Sub<T> for ModInt {type Output = ModInt;fn sub(self, rhs: T) -> Self::Output {let mut tmp = self.value;let rhs: ModInt = rhs.into();if tmp < rhs.value {tmp += MOD;}tmp -= rhs.value;if tmp >= MOD {tmp %= MOD;}Self { value: tmp }}}impl<T: Into<ModInt>> std::ops::SubAssign<T> for ModInt {fn sub_assign(&mut self, rhs: T) {*self = *self - rhs.into();}}impl<T: Into<ModInt>> std::ops::Mul<T> for ModInt {type Output = ModInt;fn mul(self, rhs: T) -> Self::Output {let rhs: ModInt = rhs.into();let mut tmp = self.value as i64 * rhs.value as i64;if tmp >= MOD as i64 {tmp %= MOD as i64;}Self { value: tmp as i32 }}}impl<T: Into<ModInt>> std::ops::MulAssign<T> for ModInt {fn mul_assign(&mut self, rhs: T) {*self = *self * rhs.into();}}impl<T: Into<ModInt>> std::ops::Div<T> for ModInt {type Output = ModInt;fn div(self, rhs: T) -> Self::Output {let rhs: ModInt = rhs.into();self * rhs.inv()}}impl<T: Into<ModInt>> std::ops::DivAssign<T> for ModInt {fn div_assign(&mut self, rhs: T) {let rhs = rhs.into();*self = *self / rhs;}}/// 二項係数を高速に計算するテーブルを作成する/// 構築 O(N)/// クエリ O(1)/// メモリ O(N)pub struct CombTable {fac: Vec<ModInt>,f_inv: Vec<ModInt>,}impl CombTable {/// O(N)で構築pub fn new(n: usize) -> Self {let mut fac = vec![ModInt::new_inner(1); n + 1];let mut f_inv = vec![ModInt::new_inner(1); n + 1];let mut inv = vec![ModInt::new_inner(1); n + 1];inv[0] = ModInt::new_inner(0);for i in 2..=n {fac[i] = fac[i - 1] * i;inv[i] = ModInt::new_inner(MOD)- inv[(MOD % i as i32) as usize] * ModInt::new_inner(MOD / i as i32);f_inv[i] = f_inv[i - 1] * inv[i];}Self { fac, f_inv }}/// nCkをO(1)で計算pub fn comb(&self, n: usize, k: usize) -> ModInt {if n < k {return ModInt::new_inner(0);}self.fac[n] * (self.f_inv[k] * self.f_inv[n - k])}}/// 加減算pub trait AddSubIdent {fn add_sub_ident() -> Self;}/// 乗除算pub trait MulDivIdent {fn mul_div_ident() -> Self;}/// GCDpub trait GCDIdent {fn gcd_ident() -> Self;}/// LCMpub trait LCMIdent {fn lcm_ident() -> Self;}/// Maxpub trait MaxIdent {fn max_ident() -> Self;}/// Minpub trait MinIdent {fn min_ident() -> Self;}/// Xorpub trait XorIdent {fn xor_ident() -> Self;}/// 変換用pub struct Num(pub i64);macro_rules! impl_num_from {($ ($ t : ty ) ,* ) => {$ (impl From < Num > for $ t {fn from (t : Num ) -> $ t {t . 0 as $ t } } ) * } ; }impl_num_from!(i8, i16, i32, i64, i128, u8, u16, u32, u64, u128, isize, usize);macro_rules! impl_num_into {($ ($ t : ty ) ,* ) => {$ (impl Into < Num > for $ t {fn into (self ) -> Num {Num (self as i64 ) } } ) * } ; }impl_num_into!(i8, i16, i32, i64, i128, u8, u16, u32, u64, u128, isize, usize);impl<T: From<Num>> AddSubIdent for T {fn add_sub_ident() -> Self {Num(0).into()}}impl<T: From<Num>> MulDivIdent for T {fn mul_div_ident() -> Self {Num(1).into()}}impl<T: From<Num>> GCDIdent for T {fn gcd_ident() -> Self {Num(0).into()}}impl<T: From<Num>> LCMIdent for T {fn lcm_ident() -> Self {Num(1).into()}}macro_rules! impl_min {($ ($ t : ident ) ,* ) => {$ (impl MinIdent for $ t {fn min_ident () -> Self {std ::$ t :: MIN } } ) * } ; }impl_min!(i8, i16, i32, i64, i128, u8, u16, u32, u64, u128, isize, usize);macro_rules! impl_max {($ ($ t : ident ) ,* ) => {$ (impl MaxIdent for $ t {fn max_ident () -> Self {std ::$ t :: MAX } } ) * } ; }impl_max!(i8, i16, i32, i64, i128, u8, u16, u32, u64, u128, isize, usize);impl<T: From<Num>> XorIdent for T {fn xor_ident() -> Self {Num(0).into()}}}fn main() {let mut sc = Scanner::new();let a = sc.next_int();let b = sc.next_int();let c = sc.next_int();let d = sc.next_int();let n = sc.next_int();let k = ModInt::new(16).pow(n as u64 / 8);let ans = match n % 8 {0 => k * (b + d),1 => k * 2 * b,2 => k * 2 * (b - c),3 => k * 4 * (-c),4 => k * (-4) * (a + c),5 => k * 8 * (-a),6 => k * 8 * (d - a),7 => k * 16 * d,_ => unreachable!(),};println!("{}", ans);}pub mod basic {pub const U_INF: u64 = (1 << 60) + (1 << 30);pub const I_INF: i64 = (1 << 60) + (1 << 30);pub struct Scanner {buf: std::collections::VecDeque<String>,reader: std::io::BufReader<std::io::Stdin>,}impl Scanner {pub fn new() -> Self {Self {buf: std::collections::VecDeque::new(),reader: std::io::BufReader::new(std::io::stdin()),}}fn scan_line(&mut self) {use std::io::BufRead;let mut flag = 0;while self.buf.is_empty() {let mut s = String::new();self.reader.read_line(&mut s).unwrap();let mut iter = s.split_whitespace().peekable();if iter.peek().is_none() {if flag >= 5 {panic!("There is no input!");}flag += 1;continue;}for si in iter {self.buf.push_back(si.to_string());}}}pub fn next<T: std::str::FromStr>(&mut self) -> T {self.scan_line();self.buf.pop_front().unwrap().parse().unwrap_or_else(|_| panic!("Couldn't parse!"))}pub fn next_usize(&mut self) -> usize {self.next()}pub fn next_int(&mut self) -> i64 {self.next()}pub fn next_uint(&mut self) -> u64 {self.next()}pub fn next_chars(&mut self) -> Vec<char> {self.next::<String>().chars().collect()}pub fn next_string(&mut self) -> String {self.next()}pub fn next_char(&mut self) -> char {self.next()}pub fn next_float(&mut self) -> f64 {self.next()}pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {(0..n).map(|_| self.next()).collect::<Vec<_>>()}}}