結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 21:39:25 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 7,299 bytes |
コンパイル時間 | 14,275 ms |
コンパイル使用メモリ | 392,660 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-17 13:49:24 |
合計ジャッジ時間 | 13,411 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
// ---------- 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 ----------// ---------- begin Precalc ----------#[allow(dead_code)]struct Precalc {inv: Vec<ModInt>,fact: Vec<ModInt>,ifact: Vec<ModInt>,}#[allow(dead_code)]impl Precalc {pub fn new(n: usize) -> Precalc {let mut inv = vec![ModInt::one(); n + 1];let mut fact = vec![ModInt::one(); n + 1];let mut ifact = vec![ModInt::one(); n + 1];for i in 2..(n + 1) {fact[i] = fact[i - 1] * ModInt(i as u32);}ifact[n] = fact[n].inv();if n > 0 {inv[n] = ifact[n] * fact[n - 1];}for i in (1..n).rev() {ifact[i] = ifact[i + 1] * ModInt((i + 1) as u32);inv[i] = ifact[i] * fact[i - 1];}Precalc {inv: inv,fact: fact,ifact: ifact,}}pub fn inv(&self, n: usize) -> ModInt {assert!(n > 0);self.inv[n]}pub fn fact(&self, n: usize) -> ModInt {self.fact[n]}pub fn ifact(&self, n: usize) -> ModInt {self.ifact[n]}pub fn comb(&self, n: usize, k: usize) -> ModInt {if k > n {return ModInt::zero();}self.fact[n] * self.ifact[k] * self.ifact[n - k]}}// ---------- end Precalc ----------// ---------- begin Matrix ----------mod matrix {use std::ops::*;pub trait SemiRing: Add<Output = Self> + Mul<Output = Self> + Copy {fn zero() -> Self;fn one() -> Self;}#[derive(Clone)]pub struct SquareMatrix<R> {size: usize,buf: Box<[R]>,}#[allow(dead_code)]impl<R: SemiRing> SquareMatrix<R> {pub fn zero(size: usize) -> Self {SquareMatrix {size: size,buf: vec![R::zero(); size * size].into_boxed_slice(),}}pub fn identity(size: usize) -> Self {let mut e = Self::zero(size);for i in 0..size {e.buf[i * size + i] = R::one();}e}pub fn set_at(&mut self, x: usize, y: usize, val: R) {assert!(x < self.size && y < self.size);self.buf[x * self.size + y] = val;}pub fn get_at(&self, x: usize, y: usize) -> R {assert!(x < self.size && y < self.size);self.buf[x * self.size + y]}pub fn matadd(&self, rhs: &Self) -> Self {assert!(self.size == rhs.size);let buf: Vec<R> = self.buf.iter().zip(rhs.buf.iter()).map(|p| *p.0 + *p.1).collect();SquareMatrix {size: self.size,buf: buf.into_boxed_slice(),}}pub fn matmul(&self, rhs: &Self) -> Self {let size = self.size;assert!(size == rhs.size);let mut res = Self::zero(size);for (x, a) in res.buf.chunks_mut(size).zip(self.buf.chunks(size)) {for (a, b) in a.iter().zip(rhs.buf.chunks(size)) {for (x, b) in x.iter_mut().zip(b.iter()) {*x = *x + *a * *b;}}}res}pub fn mat_pow(&self, mut n: usize) -> Self {let size = self.size;let mut t = Self::identity(size);let mut s = self.clone();while n > 0 {if n & 1 == 1 {t = t.matmul(&s);}s = s.matmul(&s);n >>= 1;}t}}#[allow(dead_code)]impl<R: SemiRing + Sub<Output = R>> SquareMatrix<R> {pub fn matsub(&self, rhs: &Self) -> Self {assert!(self.size == rhs.size);let buf: Vec<R> = self.buf.iter().zip(rhs.buf.iter()).map(|p| *p.0 - *p.1).collect();SquareMatrix {size: self.size,buf: buf.into_boxed_slice(),}}}}// ---------- end Matrix ----------use matrix::*;impl SemiRing for ModInt {fn zero() -> Self {ModInt::zero()}fn one() -> Self {ModInt::one()}}type M = SquareMatrix<ModInt>;fn run() {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let mut n: u64 = s.trim().parse().unwrap();let mut t = M::identity(6);let mut s = M::zero(6);for i in 1..6 {s.set_at(i, i - 1, ModInt::one());}for i in 0..6 {s.set_at(i, 5, ModInt(6).inv());}while n > 0 {if n & 1 == 1 {t = t.matmul(&s);}s = s.matmul(&s);n >>= 1;}let ans = t.get_at(5, 5);println!("{}", ans);}fn main() {run();}