結果
問題 | No.2926 Botaoshi |
ユーザー |
|
提出日時 | 2024-10-12 17:30:36 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 16,805 bytes |
コンパイル時間 | 19,864 ms |
コンパイル使用メモリ | 377,488 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 17:31:01 |
合計ジャッジ時間 | 12,237 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
use modint2::Modint998244353;use proconio::input;type Mint = Modint998244353;fn main() {input! {_n: usize,s: String,}let mut not_right = Mint::new(1);let mut right = Mint::new(0);for c in s.chars() {let mut next_not_right = Mint::new(0);let mut next_right = Mint::new(0);if c == 'L' || c == '.' {next_not_right += not_right;}if c == 'R' || c == '.' {next_right += not_right + right;}if c == 'U' || c == '.' {next_not_right += not_right + right;}not_right = next_not_right;right = next_right;}println!("{}", not_right + right);}pub mod modint2 {//! This module implements modular arithmetic.use std::{iter::{Product, Sum},ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},};type InnerType = u32;/// Returns `x` such that `a * x` is equivalent to `1` with `m` as the modulus.fn modinv(a: u32, m: u32) -> u32 {let (mut a, mut b, mut s, mut t) = (a as i64, m as i64, 1, 0);while b != 0 {let q = a / b;a -= q * b;std::mem::swap(&mut a, &mut b);s -= q * t;std::mem::swap(&mut s, &mut t);}assert_eq!(a.abs(),1,"\There is no multiplicative inverse of `a` with `m` as the modulus, \because `a` and `m` are not prime to each other (gcd(a, m) = {}).",a.abs());((s % m as i64 + m as i64) % m as i64) as u32}pub trait Reminder {/// Returns the remainder divided by `modulus`.fn reminder(self, modulus: InnerType) -> InnerType;}macro_rules! impl_reminder_for_small_unsigned_int {($($unsigned_small_int: tt), *) => {$(impl Reminder for $unsigned_small_int {fn reminder(self, modulus: InnerType) -> InnerType {self as InnerType % modulus}})*};}// Implements `Reminder` trait for `u8`, `u16` and `u32`.impl_reminder_for_small_unsigned_int!(u8, u16, u32);macro_rules! impl_reminder_for_large_unsigned_int {($($unsigned_large_int: tt), *) => {$(impl Reminder for $unsigned_large_int {fn reminder(self, modulus: InnerType) -> InnerType {(self % modulus as Self) as InnerType}})*};}// Implements `Reminder` trait for `usize`, `u64` and `u128`.impl_reminder_for_large_unsigned_int!(usize, u64, u128);macro_rules! impl_reminder_for_small_signed_int {($($signed_small_int: tt), *) => {$(impl Reminder for $signed_small_int {fn reminder(self, modulus: InnerType) -> InnerType {(self as i32 % modulus as i32 + modulus as i32) as InnerType % modulus}})*};}// Implements `Reminder` trait for `i8`, `i16` and `i32`.impl_reminder_for_small_signed_int!(i8, i16, i32);macro_rules! impl_reminder_for_large_signed_int {($($signed_large_int: tt), *) => {$(impl Reminder for $signed_large_int {fn reminder(self, modulus: InnerType) -> InnerType {(self % modulus as Self + modulus as Self) as InnerType % modulus}})*};}// Implements `Reminder` trait for `isize`, `i64` and `i128`.impl_reminder_for_large_signed_int!(isize, i64, i128);/// Structure for modular arithmetic.#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]pub struct Modint<const MODULUS: InnerType> {rem: InnerType,}impl<const MODULUS: InnerType> std::fmt::Display for Modint<MODULUS> {fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {write!(f, "{}", self.rem)}}impl<const MODULUS: InnerType> Default for Modint<MODULUS> {/// Returns a `Modint` instance equivalent to `0`.fn default() -> Self {Self::raw(0)}}impl<T, const MODULUS: InnerType> From<T> for Modint<MODULUS>whereT: Reminder,{fn from(value: T) -> Self {Self::new(value)}}impl<const MODULUS: InnerType> Add<Modint<MODULUS>> for Modint<MODULUS> {type Output = Self;fn add(self, rhs: Modint<MODULUS>) -> Self::Output {Self::raw((self.rem + rhs.rem) % MODULUS)}}impl<const MODULUS: InnerType> Sub<Modint<MODULUS>> for Modint<MODULUS> {type Output = Self;fn sub(self, rhs: Modint<MODULUS>) -> Self::Output {Self::raw((self.rem + MODULUS - rhs.rem) % MODULUS)}}impl<const MODULUS: InnerType> Mul<Modint<MODULUS>> for Modint<MODULUS> {type Output = Self;fn mul(self, rhs: Modint<MODULUS>) -> Self::Output {Self::raw((self.rem as u64 * rhs.rem as u64 % MODULUS as u64) as InnerType)}}impl<const MODULUS: InnerType> Div<Modint<MODULUS>> for Modint<MODULUS> {type Output = Self;#[allow(clippy::suspicious_arithmetic_impl)]fn div(self, rhs: Modint<MODULUS>) -> Self::Output {self * rhs.inv()}}impl<const MODULUS: InnerType> Neg for Modint<MODULUS> {type Output = Self;fn neg(self) -> Self::Output {Self::raw((MODULUS - self.rem) % MODULUS)}}impl<const MODULUS: InnerType> AddAssign<Modint<MODULUS>> for Modint<MODULUS> {fn add_assign(&mut self, rhs: Modint<MODULUS>) {*self = *self + rhs;}}impl<const MODULUS: InnerType> SubAssign<Modint<MODULUS>> for Modint<MODULUS> {fn sub_assign(&mut self, rhs: Modint<MODULUS>) {*self = *self - rhs;}}impl<const MODULUS: InnerType> MulAssign<Modint<MODULUS>> for Modint<MODULUS> {fn mul_assign(&mut self, rhs: Modint<MODULUS>) {*self = *self * rhs;}}impl<const MODULUS: InnerType> DivAssign<Modint<MODULUS>> for Modint<MODULUS> {fn div_assign(&mut self, rhs: Modint<MODULUS>) {*self = *self / rhs;}}impl<const MODULUS: InnerType, T> Add<T> for Modint<MODULUS>whereT: Reminder,{type Output = Modint<MODULUS>;fn add(self, rhs: T) -> Self::Output {self + Self::new(rhs)}}impl<const MODULUS: InnerType, T> Sub<T> for Modint<MODULUS>whereT: Reminder,{type Output = Modint<MODULUS>;fn sub(self, rhs: T) -> Self::Output {self - Self::new(rhs)}}impl<const MODULUS: InnerType, T> Mul<T> for Modint<MODULUS>whereT: Reminder,{type Output = Modint<MODULUS>;fn mul(self, rhs: T) -> Self::Output {self * Self::new(rhs)}}impl<const MODULUS: InnerType, T> Div<T> for Modint<MODULUS>whereT: Reminder,{type Output = Modint<MODULUS>;fn div(self, rhs: T) -> Self::Output {self / Self::new(rhs)}}impl<const MODULUS: InnerType, T> AddAssign<T> for Modint<MODULUS>whereT: Reminder,{fn add_assign(&mut self, rhs: T) {*self += Modint::new(rhs);}}impl<const MODULUS: InnerType, T> SubAssign<T> for Modint<MODULUS>whereT: Reminder,{fn sub_assign(&mut self, rhs: T) {*self -= Modint::new(rhs);}}impl<const MODULUS: InnerType, T> MulAssign<T> for Modint<MODULUS>whereT: Reminder,{fn mul_assign(&mut self, rhs: T) {*self *= Modint::new(rhs);}}impl<const MODULUS: InnerType, T> DivAssign<T> for Modint<MODULUS>whereT: Reminder,{fn div_assign(&mut self, rhs: T) {*self /= Modint::new(rhs);}}macro_rules! impl_ops_for_integer {($($integer:ty), *) => {$(impl<const MODULUS: InnerType> Add<Modint<MODULUS>> for $integer {type Output = Modint<MODULUS>;fn add(self, rhs: Modint<MODULUS>) -> Self::Output {Modint::new(self) + rhs}}impl<const MODULUS: InnerType> Sub<Modint<MODULUS>> for $integer {type Output = Modint<MODULUS>;fn sub(self, rhs: Modint<MODULUS>) -> Self::Output {Modint::new(self) - rhs}}impl<const MODULUS: InnerType> Mul<Modint<MODULUS>> for $integer {type Output = Modint<MODULUS>;fn mul(self, rhs: Modint<MODULUS>) -> Self::Output {Modint::new(self) * rhs}}impl<const MODULUS: InnerType> Div<Modint<MODULUS>> for $integer {type Output = Modint<MODULUS>;fn div(self, rhs: Modint<MODULUS>) -> Self::Output {Modint::new(self) / rhs}})*};}impl_ops_for_integer!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize);impl<const MODULUS: InnerType> Sum<Modint<MODULUS>> for Modint<MODULUS> {fn sum<I: Iterator<Item = Modint<MODULUS>>>(iter: I) -> Self {iter.fold(Self::new(0), |acc, x| acc + x)}}impl<'a, const MODULUS: InnerType> Sum<&'a Modint<MODULUS>> for Modint<MODULUS> {fn sum<I: Iterator<Item = &'a Modint<MODULUS>>>(iter: I) -> Self {iter.fold(Self::new(0), |acc, &x| acc + x)}}impl<const MODULUS: InnerType> Product<Modint<MODULUS>> for Modint<MODULUS> {fn product<I: Iterator<Item = Modint<MODULUS>>>(iter: I) -> Self {iter.fold(Self::new(1), |acc, x| acc * x)}}impl<'a, const MODULUS: InnerType> Product<&'a Modint<MODULUS>> for Modint<MODULUS> {fn product<I: Iterator<Item = &'a Modint<MODULUS>>>(iter: I) -> Self {iter.fold(Self::new(1), |acc, &x| acc * x)}}impl<const MODULUS: InnerType> Modint<MODULUS> {/// Returns the modulus.pub fn modulus() -> InnerType {MODULUS}/// Returns a `Modint` instance equivalent to `a`.pub fn new<T>(a: T) -> SelfwhereT: Reminder,{Self {rem: a.reminder(MODULUS),}}/// Creates a `Modint` instance from a non-negative integer less than `MODULUS`.pub fn raw(a: InnerType) -> Self {Self { rem: a }}/// Set the remainder of `Modint` instance to `a`.pub fn set_rem<T>(&mut self, a: T)whereT: Reminder,{self.rem = a.reminder(MODULUS);}/// Returns `x` such that `x * q` is equivalent to `p`.pub fn frac<T>(p: T, q: T) -> SelfwhereT: Reminder,{Self::new(p) / Self::new(q)}/// Returns the remainder divided by `MODULUS`./// The returned value is a non-negative integer less than `MODULUS`.pub fn rem(self) -> InnerType {self.rem}/// Returns the modular multiplicative inverse.pub fn inv(self) -> Self {Self {rem: modinv(self.rem, MODULUS),}}/// Calculates the power of `exp` using the iterative squaring method.pub fn pow<T>(self, exp: T) -> SelfwhereT: ToExponent,{let mut ret = Self::new(1);let mut mul = self;let exp = exp.to_exponent();let mut t = exp.abs;while t != 0 {if t & 1 == 1 {ret *= mul;}mul *= mul;t >>= 1;}if exp.neg {ret = ret.inv();}ret}}pub struct Exponent {neg: bool,abs: u128,}pub trait ToExponent {fn to_exponent(self) -> Exponent;}macro_rules! impl_to_exponent_for_unsigned_int {($($ty: tt), *) => {$(impl ToExponent for $ty {fn to_exponent(self) -> Exponent {Exponent {neg: false,abs: self as u128,}}})*};}impl_to_exponent_for_unsigned_int!(usize, u8, u16, u32, u64, u128);macro_rules! impl_to_exponent_for_signed_int {($($ty: tt), *) => {$(impl ToExponent for $ty {fn to_exponent(self) -> Exponent {Exponent {neg: self.is_negative(),abs: self.abs() as u128,}}})*};}impl_to_exponent_for_signed_int!(isize, i8, i16, i32, i64, i128);#[derive(Debug, Clone)]pub struct Factorial<Modint> {/// Upper limit of available factorial argument.upper_limit: usize,/// List of factorials.fac: Vec<Modint>,/// List of factorial inverses.inv_fac: Vec<Modint>,}impl<const MODULUS: InnerType> Factorial<Modint<MODULUS>> {/// Calculates factorial and its inverse for non-negative integers bellow `upper_limit`.pub fn new(upper_limit: usize) -> Self {let mut fac = vec![Modint::new(1); upper_limit + 1];for i in 0..upper_limit {fac[i + 1] = fac[i] * (i + 1);}let mut inv_fac = vec![fac[upper_limit].inv(); upper_limit + 1];for i in (0..upper_limit).rev() {inv_fac[i] = inv_fac[i + 1] * (i + 1);}Self {upper_limit,fac,inv_fac,}}/// Returns the factorial `n`.pub fn factorial(&self, n: usize) -> Modint<MODULUS> {assert!(n <= self.upper_limit,"The maximum number of available factorial arguments has been exceeded.");self.fac[n]}/// Returns the inverse of the factorial of `n`.pub fn inverse_factorial(&self, n: usize) -> Modint<MODULUS> {assert!(n <= self.upper_limit,"The maximum number of available factorial arguments has been exceeded.");self.inv_fac[n]}/// Calculates the number of ways to select and arrange `k` objects from `n` unique objects.pub fn permutations(&self, n: usize, k: usize) -> Modint<MODULUS> {if n >= k {self.factorial(n) * self.inverse_factorial(n - k)} else {Modint::new(0)}}/// Calculates the number of ways to select `k` objects from `n` unique objects.pub fn combinations(&self, n: usize, k: usize) -> Modint<MODULUS> {if n >= k {self.factorial(n) * self.inverse_factorial(n - k) * self.inverse_factorial(k)} else {Modint::new(0)}}/// Calculates the number of ways to select `k` objects from `n` unique objects, allowing for duplicates.pub fn combinations_with_repetition(&self, n: usize, k: usize) -> Modint<MODULUS> {if n == 0 {return if k == 0 {Modint::new(1)} else {Modint::new(0)};}self.combinations(n + k - 1, k)}}/// The type `Modint` with 1000000007 as the modulus.pub type Modint1000000007 = Modint<1000000007>;/// The type `Modint` with 998244353 as the modulus.pub type Modint998244353 = Modint<998244353>;}