結果
問題 |
No.1258 コインゲーム
|
ユーザー |
![]() |
提出日時 | 2020-10-30 18:14:55 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 4,065 bytes |
コンパイル時間 | 12,604 ms |
コンパイル使用メモリ | 399,188 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-21 22:58:08 |
合計ジャッジ時間 | 18,153 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
use std::io::{self, Write}; use std::{fmt, ops, str}; macro_rules! read { ( $t:ty ) => {{ let mut input = String::new(); io::stdin().read_line(&mut input).unwrap(); input.trim_end().parse::<$t>().ok().unwrap() }}; ( $( $t:ty ),* ) => {{ let mut input = String::new(); io::stdin().read_line(&mut input).unwrap(); let mut iter = input.split_whitespace(); ( $( iter.next().unwrap().parse::<$t>().unwrap() ),* ) }}; } struct IoStr(Vec<char>); impl str::FromStr for IoStr { type Err = (); fn from_str(s: &str) -> Result<Self, Self::Err> { Ok(IoStr(s.chars().collect())) } } impl fmt::Display for IoStr { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.0.iter().collect::<String>()) } } #[derive(Clone)] struct IoVec<T>(Vec<T>); impl<T: str::FromStr> str::FromStr for IoVec<T> { type Err = T::Err; fn from_str(s: &str) -> Result<Self, Self::Err> { let iter = s.split_whitespace(); Ok(IoVec(iter.map(|x| x.parse()).collect::<Result<_, _>>()?)) } } impl<T: fmt::Display> fmt::Display for IoVec<T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.0.iter().map(|x| x.to_string()) .collect::<Vec<_>>().join(" ") ) } } impl<T> ops::Index<usize> for IoVec<T> { type Output = T; fn index(&self, i: usize) -> &Self::Output { self.0.get(i - 1).unwrap() } } impl<T> ops::IndexMut<usize> for IoVec<T> { fn index_mut(&mut self, i: usize) -> &mut Self::Output { self.0.get_mut(i - 1).unwrap() } } #[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)] struct ModInt(i64); impl ModInt { const MOD: i64 = 1_000_000_007; fn new(x: i64) -> ModInt { Self(x % Self::MOD) } } impl ops::Add for ModInt { type Output = Self; fn add(self, other: Self) -> Self { let x = self.0 + other.0; Self( if x < Self::MOD { x } else { x - Self::MOD } ) } } impl ops::AddAssign for ModInt { fn add_assign(&mut self, other: Self) { *self = *self + other; } } impl ops::Sub for ModInt { type Output = Self; fn sub(self, other: Self) -> Self { if self.0 < other.0 { Self(self.0 + Self::MOD - other.0) } else { Self(self.0 - other.0) } } } impl ops::SubAssign for ModInt { fn sub_assign(&mut self, other: Self) { *self = *self - other; } } impl ops::Mul for ModInt { type Output = Self; fn mul(self, other: Self) -> Self { Self::new(self.0 * other.0) } } impl ops::MulAssign for ModInt { fn mul_assign(&mut self, other: Self) { *self = *self * other; } } impl std::fmt::Display for ModInt { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl std::str::FromStr for ModInt { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result<Self, Self::Err> { let x = s.parse()?; Ok(ModInt(x)) } } impl From<usize> for ModInt { fn from(x: usize) -> Self { Self(x as i64) } } impl ModInt { fn pow(mut self, mut n: i64) -> Self { let mut res = Self::new(1); while n > 0 { if n & 1 > 0 { res *= self; } self *= self; n >>= 1; } res } fn inv(self) -> Self { self.pow(Self::MOD - 2) } } fn solve(writer: &mut io::BufWriter<io::StdoutLock>) { let (n, m, x) = read!(i64, ModInt, u8); let a = (ModInt(1) + m).pow(n); let b = (ModInt(1) - m).pow(n); if x == 0 { writeln!(writer, "{}", (a + b) * ModInt(2).inv()).ok(); } else { writeln!(writer, "{}", (a - b) * ModInt(2).inv()).ok(); } } fn main() { let stdout = io::stdout(); let mut writer = io::BufWriter::new(stdout.lock()); for _ in 0..read!(usize) { solve(&mut writer); } }