Avoid K Palindrome の解説

dp[s(i-k..=i)] := i-k..=iの文字列がs(i-k..=i)の場合の数 として、dpする。

遷移は、'?'だったら'A' or 'B'にいって、かつ回文チェックにクリアすれば遷移する。

fn main() {
    input! {
        n: usize,
        k: usize,
        s: Chars
    }
    let check = |s: &VecDeque<char>| {
        for i in 0..s.len() {
            if s[i] != s[s.len() - i - 1] {
                return true;
            }
        }
        false
    };
    let mut dp = {
        let mut dp = HashMap::new();
        let mut v = vec![];
        for i in 0..k {
            v.push(s[i]);
        }
        let idxs = v.iter().positions(|&e| e == '?').collect_vec();
        for p in (0..=1).product_repeat(idxs.len()) {
            let mut target = VecDeque::from(v.to_owned());
            for i in 0..idxs.len() {
                let t = if p[i] == 0 {'A'} else {'B'};
                target[idxs[i]] = t;
            }
            if !check(&target) {
                continue;
            }
            dp.insert(target, ModInt998244353::new(1));
        }
        dp
    };
    for i in k..n {
        let c = s[i];
        let next = if c == 'A' {vec!['A']} else if c == 'B' {vec!['B']} else {vec!['A', 'B']};
        let mut new = HashMap::new();
        for row in dp.iter() {
            let &cur = row.1;
            let mut row = row.0.to_owned();
            row.pop_front().unwrap();
            for &c in next.iter() {
                row.push_back(c);
                if check(&row) {
                    let &pre = new.get(&row).unwrap_or(&ModInt998244353::new(0));
                    new.insert(row.to_owned(), cur + pre);
                }
                row.pop_back().unwrap();
            }
        }
        swap(&mut dp, &mut new);
    }
    let ans = dp.values().sum::<ModInt998244353>();
    println!("{}", ans);
}