結果
問題 | No.1492 01文字列と転倒 |
ユーザー |
![]() |
提出日時 | 2021-04-30 22:20:03 |
言語 | Rust (1.83.0 + proconio) |
結果 |
RE
|
実行時間 | - |
コード長 | 6,578 bytes |
コンパイル時間 | 13,051 ms |
コンパイル使用メモリ | 378,784 KB |
実行使用メモリ | 17,664 KB |
最終ジャッジ日時 | 2024-07-19 01:47:06 |
合計ジャッジ時間 | 19,231 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 2 |
other | RE * 22 |
コンパイルメッセージ
warning: methods `pow` and `inv` are never used --> src/main.rs:85:8 | 66 | impl Modulo { | ----------- methods in this implementation ... 85 | fn pow(self, p: i64) -> Modulo { | ^^^ ... 97 | fn inv(self) -> Modulo { | ^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
#![allow(unused_imports)]use std::cmp::*;use std::collections::*;use std::io::Write;use std::ops::Bound::*;#[allow(unused_macros)]macro_rules! debug {($($e:expr),*) => {#[cfg(debug_assertions)]$({let (e, mut err) = (stringify!($e), std::io::stderr());writeln!(err, "{} = {:?}", e, $e).unwrap()})*};}fn main() {let v = read_vec::<i64>();let (n, m) = (v[0] as usize, v[1]);Modulo::set_modulus(m);let mut dp = vec![vec![Modulo(0); n * n + 1]; n + 1];let mut next = vec![vec![Modulo(0); n * n + 1]; n + 1];dp[0][0] += 1;for i in 0..2 * n {for j in 0..=n * n {for k in 0..=n {next[k][j] = Modulo(0);}}for prev_reversed in 0..=n * i {for prev_zero_used in 0..=min(i, n) {let prev_one_used = i - prev_zero_used;if prev_zero_used < n && prev_reversed + prev_one_used <= n * n {next[prev_zero_used + 1][prev_reversed + prev_one_used] +=dp[prev_zero_used][prev_reversed];}if prev_zero_used > prev_one_used {next[prev_zero_used][prev_reversed] += dp[prev_zero_used][prev_reversed];}}}std::mem::swap(&mut dp, &mut next);}for &ans in &dp[n] {println!("{}", ans);}}fn read<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}fn read_vec<T: std::str::FromStr>() -> Vec<T> {read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()}#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]struct Modulo(i64);static mut MODULUS: i64 = 1000_000_000 + 7;impl Modulo {fn set_modulus(m: i64) {unsafe {MODULUS = m;}}fn get_modulus() -> i64 {unsafe { MODULUS }}fn new(x: i64) -> Modulo {let m = Modulo::get_modulus();if x < 0 {Modulo(x % m + m)} else if x < m {Modulo(x)} else {Modulo(x % m)}}fn pow(self, p: i64) -> Modulo {if p == 0 {Modulo(1)} else {let mut t = self.pow(p / 2);t *= t;if p & 1 == 1 {t *= self;}t}}fn inv(self) -> Modulo {self.pow(Modulo::get_modulus() - 2)}}impl std::fmt::Display for Modulo {fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {self.0.fmt(f)}}impl std::ops::AddAssign for Modulo {fn add_assign(&mut self, other: Modulo) {let m = Modulo::get_modulus();self.0 += other.0;if self.0 >= m {self.0 -= m;}}}impl std::ops::MulAssign for Modulo {fn mul_assign(&mut self, other: Modulo) {let m = Modulo::get_modulus();self.0 *= other.0;self.0 %= m;}}impl std::ops::SubAssign for Modulo {fn sub_assign(&mut self, other: Modulo) {let m = Modulo::get_modulus();self.0 += m - other.0;if self.0 >= m {self.0 -= m;}}}macro_rules! impl_modulo_ops {($imp:ident, $method:ident, $assign_imp:ident, $assign_method:ident) => {impl<'a> std::ops::$assign_imp<&'a Modulo> for Modulo {fn $assign_method(&mut self, other: &'a Modulo) {std::ops::$assign_imp::$assign_method(self, *other);}}impl std::ops::$imp for Modulo {type Output = Modulo;fn $method(self, other: Modulo) -> Modulo {let mut x = self;std::ops::$assign_imp::$assign_method(&mut x, other);x}}impl<'a> std::ops::$imp<Modulo> for &'a Modulo {type Output = Modulo;fn $method(self, other: Modulo) -> Modulo {std::ops::$imp::$method(*self, other)}}impl<'a> std::ops::$imp<&'a Modulo> for Modulo {type Output = Modulo;fn $method(self, other: &'a Modulo) -> Modulo {std::ops::$imp::$method(self, *other)}}impl<'a, 'b> std::ops::$imp<&'b Modulo> for &'a Modulo {type Output = Modulo;fn $method(self, other: &'b Modulo) -> Modulo {std::ops::$imp::$method(*self, *other)}}impl std::ops::$assign_imp<i64> for Modulo {fn $assign_method(&mut self, other: i64) {std::ops::$assign_imp::$assign_method(self, Modulo::new(other));}}impl<'a> std::ops::$assign_imp<&'a i64> for Modulo {fn $assign_method(&mut self, other: &'a i64) {std::ops::$assign_imp::$assign_method(self, *other);}}impl std::ops::$imp<i64> for Modulo {type Output = Modulo;fn $method(self, other: i64) -> Modulo {let mut x = self;std::ops::$assign_imp::$assign_method(&mut x, other);x}}impl<'a> std::ops::$imp<&'a i64> for Modulo {type Output = Modulo;fn $method(self, other: &'a i64) -> Modulo {std::ops::$imp::$method(self, *other)}}impl<'a> std::ops::$imp<i64> for &'a Modulo {type Output = Modulo;fn $method(self, other: i64) -> Modulo {std::ops::$imp::$method(*self, other)}}impl<'a, 'b> std::ops::$imp<&'b i64> for &'a Modulo {type Output = Modulo;fn $method(self, other: &'b i64) -> Modulo {std::ops::$imp::$method(*self, *other)}}};}impl_modulo_ops!(Add, add, AddAssign, add_assign);impl_modulo_ops!(Mul, mul, MulAssign, mul_assign);impl_modulo_ops!(Sub, sub, SubAssign, sub_assign);use std::iter::Sum;impl Sum for Modulo {fn sum<I>(iter: I) -> SelfwhereI: Iterator<Item = Modulo>,{iter.fold(Modulo(0), |a, b| a + b)}}impl<'a> Sum<&'a Modulo> for Modulo {fn sum<I>(iter: I) -> SelfwhereI: Iterator<Item = &'a Self>,{iter.fold(Modulo(0), |a, b| a + b)}}