結果
問題 | No.1049 Zero (Exhaust) |
ユーザー |
![]() |
提出日時 | 2020-05-08 21:33:33 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 2,899 bytes |
コンパイル時間 | 23,785 ms |
コンパイル使用メモリ | 381,348 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 00:05:00 |
合計ジャッジ時間 | 13,701 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
// ---------- begin ModInt ----------const MOD: u32 = 1_000_000_007;#[derive(Clone, Copy)]struct ModInt(u32);impl std::ops::Add for ModInt {type Output = ModInt;fn add(self, rhs: ModInt) -> Self::Output {let mut d = self.0 + rhs.0;if d >= MOD {d -= MOD;}ModInt(d)}}impl std::ops::AddAssign for ModInt {fn add_assign(&mut self, rhs: ModInt) {*self = *self + rhs;}}impl std::ops::Sub for ModInt {type Output = ModInt;fn sub(self, rhs: ModInt) -> Self::Output {let mut d = self.0 + MOD - rhs.0;if d >= MOD {d -= MOD;}ModInt(d)}}impl std::ops::SubAssign for ModInt {fn sub_assign(&mut self, rhs: ModInt) {*self = *self - rhs;}}impl std::ops::Mul for ModInt {type Output = ModInt;fn mul(self, rhs: ModInt) -> Self::Output {ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32)}}impl std::ops::MulAssign for ModInt {fn mul_assign(&mut self, rhs: ModInt) {*self = *self * rhs;}}impl std::ops::Neg for ModInt {type Output = ModInt;fn neg(self) -> Self::Output {ModInt(if self.0 == 0 {0} else {MOD - self.0})}}impl std::fmt::Display for ModInt {fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> 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 val = s.parse::<u32>()?;Ok(ModInt::new(val))}}impl From<usize> for ModInt {fn from(val: usize) -> ModInt {ModInt((val % MOD as usize) as u32)}}#[allow(dead_code)]impl ModInt {pub fn new(n: u32) -> ModInt {ModInt(n % MOD)}pub fn zero() -> ModInt {ModInt(0)}pub fn one() -> ModInt {ModInt(1)}pub fn pow(self, mut n: u32) -> ModInt {let mut t = ModInt::one();let mut s = self;while n > 0 {if n & 1 == 1 {t *= s;}s *= s;n >>= 1;}t}pub fn inv(self) -> ModInt {assert!(self.0 > 0);self.pow(MOD - 2)}}// ---------- end ModInt ----------fn run() {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let mut it = s.trim().split_whitespace();let p: ModInt = it.next().unwrap().parse().unwrap();let k: usize = it.next().unwrap().parse().unwrap();let one = ModInt::one();let mut x = ModInt::one();let mut y = ModInt::zero();for _ in 0..k {let a = (p + one) * x + ModInt(2) * y;let b = (p - one) * x + ModInt(2) * (p - one) * y;x = a;y = b;}println!("{}", x);}fn main() {run();}