結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-04-24 21:35:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 90 ms / 2,000 ms |
コード長 | 5,553 bytes |
コンパイル時間 | 13,203 ms |
コンパイル使用メモリ | 379,408 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 02:28:21 |
合計ジャッジ時間 | 14,253 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#![allow(unused)]use kyoproio::*;use std::{collections::*,io::{self, prelude::*},iter,mem::{replace, swap},};fn main() -> io::Result<()> {std::thread::Builder::new().stack_size(64 * 1024 * 1024).spawn(solve)?.join().unwrap();Ok(())}fn solve() {let stdin = io::stdin();let mut kin = KInput::new(stdin.lock());let stdout = io::stdout();let mut out = io::BufWriter::new(stdout.lock());macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+) }; }macro_rules! outputln {($($args:expr),+) => { output!($($args),+); outputln!(); };() => { output!("\n"); if cfg!(debug_assertions) { out.flush(); } }}const MOD: i64 = 1e9 as i64 + 7;let (n, m): (i64, i64) = kin.input();let c = Combination::new(100001, MOD);let mut ans = 0;let mut sign = 1;for i in (1..=m).rev() {ans += MOD + sign * (c.comb(m, i) * c.pow(i, n) % MOD);ans %= MOD;sign = -sign;}outputln!("{}", ans);}pub fn mod_pow(mut a: i64, mut b: i64, m: i64) -> i64 {let mut y = 1;while b > 0 {if b & 1 == 1 {y = y * a % m;}a = a * a % m;b >>= 1;}y}pub fn mod_inv(x: i64, m: i64) -> i64 {mod_pow(x, m - 2, m)}pub struct Combination {m: i64,fact: Vec<i64>,}impl Combination {pub fn new(size: usize, m: i64) -> Self {let mut comb = Self {m,fact: Vec::new(),};comb.resize(size);comb}pub fn resize(&mut self, size: usize) {let old_len = self.fact.len();self.fact.resize(size + 1, 0);for i in old_len..=size {self.fact[i] = if i == 0 {1} else {i as i64 * self.fact[i - 1] % self.m};}}pub fn fact(&self, x: i64) -> i64 {self.fact[x as usize]}pub fn perm(&self, a: i64, b: i64) -> i64 {if a >= b {self.fact(a) * self.inv(self.fact(a - b)) % self.m} else {0}}pub fn comb(&self, a: i64, b: i64) -> i64 {if a >= b {self.fact(a) * self.inv(self.fact(b) * self.fact(a - b) % self.m) % self.m} else {0}}pub fn pow(&self, a: i64, b: i64) -> i64 {mod_pow(a, b, self.m)}pub fn inv(&self, x: i64) -> i64 {self.pow(x, self.m - 2)}}// -----------------------------------------------------------------------------pub mod kyoproio {#![warn(unused)]use std::io::prelude::*;pub trait Input {fn str(&mut self) -> &str;fn input<T: InputParse>(&mut self) -> T {T::input(self)}fn iter<T: InputParse>(&mut self) -> Iter<T, Self> {Iter(self, std::marker::PhantomData)}fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B {self.iter().take(n).collect()}}pub struct KInput<R> {src: R,buf: String,pos: usize,}impl<R: BufRead> KInput<R> {pub fn new(src: R) -> Self {Self {src,buf: String::with_capacity(1024),pos: 0,}}}impl<R: BufRead> Input for KInput<R> {fn str(&mut self) -> &str {loop {if self.pos >= self.buf.len() {self.pos = 0;self.buf.clear();if self.src.read_line(&mut self.buf).expect("io error") == 0 {return &self.buf;}}let range = self.pos..self.buf[self.pos..].find(|c: char| c.is_ascii_whitespace()).map(|i| i + self.pos).unwrap_or_else(|| self.buf.len());self.pos = range.end + 1;if range.end > range.start {return &self.buf[range];}}}}pub struct Iter<'a, T, I: ?Sized>(&'a mut I, std::marker::PhantomData<*const T>);impl<'a, T: InputParse, I: Input + ?Sized> Iterator for Iter<'a, T, I> {type Item = T;fn next(&mut self) -> Option<T> {Some(self.0.input())}}pub trait InputParse: Sized {fn input<I: Input + ?Sized>(src: &mut I) -> Self;}impl InputParse for Vec<u8> {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().as_bytes().to_owned()}}macro_rules! from_str_impl {{ $($T:ty)* } => {$(impl InputParse for $T {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().parse::<$T>().expect("parse error")}})*}}from_str_impl! {String char bool f32 f64 isize i8 i16 i32 i64 i128 usize u8 u16 u32 u64 u128}macro_rules! tuple_impl {($H:ident $($T:ident)*) => {impl<$H: InputParse, $($T: InputParse),*> InputParse for ($H, $($T),*) {fn input<I: Input + ?Sized>(src: &mut I) -> Self {($H::input(src), $($T::input(src)),*)}}tuple_impl!($($T)*);};() => {}}tuple_impl!(A B C D E F G);}