#689545 (Rust) No.1646 Avoid Palindrome

提出ソース

結果

問題	No.1646 Avoid Palindrome
ユーザー	Rheo Tommy
提出日時	2021-08-13 23:11:19
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	620 ms / 3,000 ms
コード長	11,078 bytes
コンパイル時間	14,679 ms
コンパイル使用メモリ	379,800 KB
実行使用メモリ	211,840 KB
最終ジャッジ日時	2024-11-08 15:55:54
合計ジャッジ時間	34,418 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	534 ms 198,656 KB
testcase_05	AC	530 ms 198,656 KB
testcase_06	AC	514 ms 192,000 KB
testcase_07	AC	534 ms 198,528 KB
testcase_08	AC	537 ms 200,448 KB
testcase_09	AC	511 ms 190,592 KB
testcase_10	AC	525 ms 195,328 KB
testcase_11	AC	505 ms 189,952 KB
testcase_12	AC	532 ms 198,272 KB
testcase_13	AC	537 ms 200,448 KB
testcase_14	AC	571 ms 195,968 KB
testcase_15	AC	582 ms 199,808 KB
testcase_16	AC	568 ms 194,688 KB
testcase_17	AC	587 ms 203,264 KB
testcase_18	AC	571 ms 197,760 KB
testcase_19	AC	603 ms 196,864 KB
testcase_20	AC	584 ms 198,528 KB
testcase_21	AC	581 ms 203,008 KB
testcase_22	AC	563 ms 196,096 KB
testcase_23	AC	588 ms 204,160 KB
testcase_24	AC	614 ms 211,840 KB
testcase_25	AC	613 ms 211,840 KB
testcase_26	AC	611 ms 211,840 KB
testcase_27	AC	620 ms 211,840 KB
testcase_28	AC	619 ms 211,840 KB
testcase_29	AC	514 ms 208,640 KB
testcase_30	AC	514 ms 208,640 KB
testcase_31	AC	520 ms 208,640 KB
testcase_32	AC	513 ms 208,768 KB
testcase_33	AC	511 ms 208,640 KB
testcase_34	AC	611 ms 211,840 KB
testcase_35	AC	1 ms 5,248 KB
testcase_36	AC	1 ms 5,248 KB
testcase_37	AC	1 ms 5,248 KB
testcase_38	AC	1 ms 5,248 KB
testcase_39	AC	1 ms 5,248 KB
testcase_40	AC	1 ms 5,248 KB
testcase_41	AC	1 ms 5,248 KB
testcase_42	AC	1 ms 5,248 KB
testcase_43	AC	512 ms 208,640 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

// # ファイル構成
// - use 宣言
// - lib モジュール
// - main 関数
// - basic モジュール
//
// 常に使うテンプレートライブラリは basic モジュール内にあります。
// 問題に応じて使うライブラリ lib モジュール内にコピペしています。
// ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder
// Twitter はこちら → https://twitter.com/RheoTommy

use std::collections::*;
use std::io::{stdout, BufWriter, Write};

use crate::basic::*;
use crate::lib::*;

pub mod lib {
    pub type ModInt = StaticModInt;

    pub const MOD: i32 = MOD998244353;
    pub const MOD1000000007: i32 = 1000000007;
    pub const MOD998244353: i32 = 998244353;

    #[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
    pub struct StaticModInt(i32);

    impl std::fmt::Display for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl std::fmt::Debug for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self)
        }
    }

    impl StaticModInt {
        pub fn new<T: Into<StaticModInt>>(n: T) -> Self {
            n.into()
        }
        fn new_inner(n: i32) -> Self {
            Self(n)
        }
        pub fn pow<T: Into<Int>>(self, n: T) -> Self {
            let n: Int = n.into();
            let mut n = n.0;
            assert!(n >= 0);
            let mut res = StaticModInt::new(1);
            let mut x = self;
            while n != 0 {
                if n & 1 == 1 {
                    res *= x;
                }
                n /= 2;
                x *= x;
            }
            res
        }
        pub fn inv(self) -> Self {
            self.pow((MOD - 2) as u64)
        }
    }

    impl<T: Into<Int>> From<T> for StaticModInt {
        fn from(t: T) -> Self {
            let n: Int = t.into();
            let n = (n.0 % MOD as i64) as i32;
            if n < 0 {
                Self::new_inner(n + MOD)
            } else {
                Self::new_inner(n)
            }
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Add<T> for StaticModInt {
        type Output = Self;
        fn add(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp += t.0;
            if tmp >= MOD {
                tmp -= MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::AddAssign<T> for StaticModInt {
        fn add_assign(&mut self, rhs: T) {
            *self = *self + rhs.into()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Sub<T> for StaticModInt {
        type Output = Self;
        fn sub(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp -= t.0;
            if tmp < 0 {
                tmp += MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::SubAssign<T> for StaticModInt {
        fn sub_assign(&mut self, rhs: T) {
            *self = *self - rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Mul<T> for StaticModInt {
        type Output = Self;
        fn mul(self, rhs: T) -> Self::Output {
            let mut tmp = self.0 as i64;
            let t: StaticModInt = rhs.into();
            tmp *= t.0 as i64;
            if tmp >= MOD as i64 {
                tmp %= MOD as i64;
            }
            let tmp = tmp as i32;
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::MulAssign<T> for StaticModInt {
        fn mul_assign(&mut self, rhs: T) {
            *self = *self * rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Div<T> for StaticModInt {
        type Output = Self;
        fn div(self, rhs: T) -> Self::Output {
            let t: StaticModInt = rhs.into();
            self * t.inv()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::DivAssign<T> for StaticModInt {
        fn div_assign(&mut self, rhs: T) {
            *self = *self / rhs.into();
        }
    }

    /// 二項係数を高速に計算するテーブルを作成する
    /// 構築 O(N)
    /// クエリ O(1)
    /// メモリ O(N)
    pub struct CombTable {
        fac: Vec<ModInt>,
        f_inv: Vec<ModInt>,
    }

    impl CombTable {
        /// O(N)で構築
        pub fn new<T: Into<Int>>(n: T) -> Self {
            let n: Int = n.into();
            assert!(n.0 >= 0);
            let n = n.0 as usize;
            let mut fac = vec![ModInt::new(1); n + 1];
            let mut f_inv = vec![ModInt::new(1); n + 1];
            let mut inv = vec![ModInt::new(1); n + 1];
            inv[0] = ModInt::new(0);
            for i in 2..=n {
                fac[i] = fac[i - 1] * i;
                inv[i] =
                    ModInt::new(MOD) - inv[(MOD % i as i32) as usize] * ModInt::new(MOD / i as i32);
                f_inv[i] = f_inv[i - 1] * inv[i];
            }
            Self { fac, f_inv }
        }
        /// nCkをO(1)で計算
        pub fn comb<T1: Into<Int>, T2: Into<Int>>(&self, n: T1, k: T2) -> ModInt {
            let n: Int = n.into();
            let k: Int = k.into();
            assert!(n.0 >= 0);
            assert!(k.0 >= 0);
            let n = n.0 as usize;
            let k = k.0 as usize;
            if n < k {
                return ModInt::new(0);
            }
            self.fac[n] * (self.f_inv[k] * self.f_inv[n - k])
        }
    }

    #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug)]
    pub struct Int(pub i64);
    macro_rules! impl_int_from {($ ($ t : ty ) ,* ) => {$ (impl From < Int > for $ t {fn from (t : Int ) -> $ t {t . 0 as $ t } } ) * } ; }
    impl_int_from!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
    macro_rules! impl_int_into {($ ($ t : ty ) ,* ) => {$ (impl Into < Int > for $ t {fn into (self ) -> Int {Int (self as i64 ) } } ) * } ; }
    impl_int_into!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
}

fn main() {
    unsafe { mains(); }
}

#[target_feature(enable = "aes,avx,avx2,bmi1,bmi2,fma,fxsr,pclmulqdq,popcnt,rdrand,rdseed,sse,sse2,sse4.1,sse4.2,ssse3,xsave,xsavec,xsaveopt,xsaves")]
unsafe fn mains() {
    let mut io = IO::new();
    let n = io.next_usize();
    let s = io.next_chars().collect::<Vec<_>>();
    let mut memo = vec![HashSet::new(); n];
    for i in 0..n {
        if s[i] == '?' {
            for c in 0..26 {
                memo[i].insert(to_char(c));
            }
        } else {
            memo[i].insert(s[i]);
        }
    }

    for i in 0..n - 1 {
        let j = i + 1;
        if s[i] != '?' {
            memo[j].remove(&s[i]);
        }
        if s[j] != '?' {
            memo[i].remove(&s[j]);
        }
    }

    for center in 1..n - 1 {
        let l = center - 1;
        let r = center + 1;
        if s[l] != '?' {
            memo[r].remove(&s[l]);
        }
        if s[r] != '?' {
            memo[l].remove(&s[r]);
        }
    }

    let memo = memo.into_iter().map(|hm| hm.into_iter().collect::<Vec<_>>()).collect::<Vec<_>>();

    let mut dp = vec![vec![vec![ModInt::new(0); 27]; 27]; n + 1];
    *dp.get_unchecked_mut(0).get_unchecked_mut(26).get_unchecked_mut(26) += 1;
    for i in 0..n {
        let mut sum = vec![ModInt::new(0); 27];
        let mut ng = vec![vec![ModInt::new(0); 27]; 27];
        for s in 0..27 {
            for t in 0..27 {
                let tmp = *dp.get_unchecked(i).get_unchecked(s).get_unchecked(t);
                sum[t] += tmp;
                ng[t][s] += tmp;
                ng[t][t] += tmp;
            }
        }
        for &c in &memo[i] {
            for t in 0..27 {
                *dp.get_unchecked_mut(i + 1).get_unchecked_mut(t).get_unchecked_mut(to_index(c)) += sum[t] - ng[t][to_index(c)];
            }
        }
    }

    let mut ans = ModInt::new(0);
    for s in 0..27 {
        for t in 0..27 {
            ans += dp[n][s][t];
        }
    }

    io.println(ans);
}

fn to_index(c: char) -> usize { (c as u8 - b'a') as usize }

fn to_char(u: usize) -> char { (b'a' + u as u8) as char }

pub mod basic {
    pub const U_INF: u64 = (1 << 60) + (1 << 30);
    pub const I_INF: i64 = (1 << 60) + (1 << 30);

    pub struct IO {
        iter: std::str::SplitAsciiWhitespace<'static>,
        buf: std::io::BufWriter<std::io::StdoutLock<'static>>,
    }

    impl Default for IO {
        fn default() -> Self {
            Self::new()
        }
    }

    impl IO {
        pub fn new() -> Self {
            use std::io::*;
            let mut input = String::new();
            std::io::stdin().read_to_string(&mut input).unwrap();
            let input = Box::leak(input.into_boxed_str());
            let out = Box::new(stdout());
            IO {
                iter: input.split_ascii_whitespace(),
                buf: BufWriter::new(Box::leak(out).lock()),
            }
        }
        pub fn next_str(&mut self) -> &str {
            self.iter.next().unwrap()
        }
        pub fn read<T: std::str::FromStr>(&mut self) -> T
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            self.iter.next().unwrap().parse().unwrap()
        }
        pub fn next_usize(&mut self) -> usize {
            self.read()
        }
        pub fn next_uint(&mut self) -> u64 {
            self.read()
        }
        pub fn next_int(&mut self) -> i64 {
            self.read()
        }
        pub fn next_float(&mut self) -> f64 {
            self.read()
        }
        pub fn next_chars(&mut self) -> std::str::Chars {
            self.next_str().chars()
        }
        pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T>
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            (0..n).map(|_| self.read()).collect::<Vec<_>>()
        }
        pub fn print<T: std::fmt::Display>(&mut self, t: T) {
            use std::io::Write;
            write!(self.buf, "{}", t).unwrap();
        }
        pub fn println<T: std::fmt::Display>(&mut self, t: T) {
            self.print(t);
            self.print("\n");
        }
        pub fn print_iter<T: std::fmt::Display, I: Iterator<Item=T>>(
            &mut self,
            mut iter: I,
            sep: &str,
        ) {
            if let Some(v) = iter.next() {
                self.print(v);
                for vi in iter {
                    self.print(sep);
                    self.print(vi);
                }
            }
            self.print("\n");
        }
        pub fn flush(&mut self) {
            use std::io::Write;
            self.buf.flush().unwrap();
        }
    }
}

yukicoder

結果

テストケース

ソースコード