結果

問題 No.1646 Avoid Palindrome
ユーザー Rheo TommyRheo Tommy
提出日時 2021-08-13 22:36:00
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 2,573 ms / 3,000 ms
コード長 10,815 bytes
コンパイル時間 13,926 ms
コンパイル使用メモリ 390,416 KB
実行使用メモリ 156,288 KB
最終ジャッジ日時 2024-10-03 20:32:20
合計ジャッジ時間 61,858 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 129 ms
144,384 KB
testcase_01 AC 128 ms
144,384 KB
testcase_02 AC 129 ms
144,256 KB
testcase_03 AC 129 ms
144,384 KB
testcase_04 AC 504 ms
152,064 KB
testcase_05 AC 509 ms
152,064 KB
testcase_06 AC 497 ms
151,808 KB
testcase_07 AC 495 ms
152,192 KB
testcase_08 AC 498 ms
152,320 KB
testcase_09 AC 480 ms
151,680 KB
testcase_10 AC 487 ms
151,936 KB
testcase_11 AC 471 ms
151,680 KB
testcase_12 AC 506 ms
152,064 KB
testcase_13 AC 494 ms
152,320 KB
testcase_14 AC 2,282 ms
155,264 KB
testcase_15 AC 2,333 ms
155,520 KB
testcase_16 AC 2,273 ms
155,264 KB
testcase_17 AC 2,368 ms
155,776 KB
testcase_18 AC 2,324 ms
155,392 KB
testcase_19 AC 2,334 ms
155,392 KB
testcase_20 AC 2,364 ms
155,520 KB
testcase_21 AC 2,388 ms
155,648 KB
testcase_22 AC 2,320 ms
155,264 KB
testcase_23 AC 2,394 ms
155,776 KB
testcase_24 AC 2,506 ms
156,288 KB
testcase_25 AC 2,475 ms
156,160 KB
testcase_26 AC 2,573 ms
156,288 KB
testcase_27 AC 2,465 ms
156,160 KB
testcase_28 AC 2,473 ms
156,160 KB
testcase_29 AC 225 ms
150,272 KB
testcase_30 AC 222 ms
150,272 KB
testcase_31 AC 221 ms
150,144 KB
testcase_32 AC 225 ms
150,144 KB
testcase_33 AC 226 ms
150,144 KB
testcase_34 AC 2,500 ms
156,288 KB
testcase_35 AC 130 ms
144,384 KB
testcase_36 AC 154 ms
144,384 KB
testcase_37 AC 134 ms
144,256 KB
testcase_38 AC 134 ms
144,256 KB
testcase_39 AC 128 ms
144,384 KB
testcase_40 AC 129 ms
144,256 KB
testcase_41 AC 129 ms
144,384 KB
testcase_42 AC 129 ms
144,384 KB
testcase_43 AC 224 ms
150,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![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 = [[[ModInt::new(0); 27]; 27]; 5 * 10000 + 1];
    dp[0][26][26] += 1;
    for i in 0..n {
        for s in 0..27 {
            for t in 0..27 {
                let tmp = dp[i][s][t];
                if tmp == ModInt::new(0) { continue; }
                for &c in &memo[i] {
                    if to_index(c) != s && to_index(c) != t {
                        dp[i + 1][t][to_index(c)] += tmp;
                    }
                }
            }
        }
    }

    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();
        }
    }
}
0