結果
| 問題 | No.1050 Zero (Maximum) |
| ユーザー |
 akakimidori
|
| 提出日時 | 2020-05-08 21:38:53 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 11 ms / 2,000 ms |
| コード長 | 6,150 bytes |
| コンパイル時間 | 11,095 ms |
| コンパイル使用メモリ | 389,660 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-04 00:11:58 |
| 合計ジャッジ時間 | 12,271 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 |
ソースコード
// ---------- 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 Matrix ----------mod matrix {use std;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()}}fn run() {let mut s = String::new();std::io::stdin().read_line(&mut s).unwrap();let mut it = s.trim().split_whitespace();let n: usize = it.next().unwrap().parse().unwrap();let k: usize = it.next().unwrap().parse().unwrap();type M = SquareMatrix<ModInt>;let mut s = M::zero(n);for i in 0..n {for j in 0..n {let x = (i + j) % n;let v = s.get_at(i, x) + ModInt::one();s.set_at(i, x, v);let x = i * j % n;let v = s.get_at(i, x) + ModInt::one();s.set_at(i, x, v);}}let t = s.mat_pow(k);let ans = t.get_at(0, 0);println!("{}", ans);}fn main() {run();}