結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-04-24 21:40:58 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 4,021 bytes |
コンパイル時間 | 13,071 ms |
コンパイル使用メモリ | 390,176 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 02:36:09 |
合計ジャッジ時間 | 14,091 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
コンパイルメッセージ
warning: unused import: `std::io::Read` --> src/main.rs:153:5 | 153 | use std::io::Read; | ^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default
ソースコード
// ---------- 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) {inv[i] = -inv[MOD as usize % i] * ModInt(MOD / i as u32);fact[i] = fact[i - 1] * ModInt(i as u32);ifact[i] = ifact[i - 1] * inv[i];}Precalc {inv: inv,fact: fact,ifact: ifact,}}pub fn inv(&self, n: usize) -> ModInt {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 ----------use std::io::Read;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 m: usize = it.next().unwrap().parse().unwrap();let pc = Precalc::new(n + m);let mut ans = ModInt::zero();let mut sign = ModInt::one();for i in (0..=m).rev() {ans += sign * pc.comb(m, i) * ModInt::from(i).pow(n as u32);sign = -sign;}println!("{}", ans);}fn main() {run();}