Atcoder_dp_impossível

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u = unsigned;
constexpr u MOD = 998244353;


// Função para verificar se um número binário representa um palíndromo
bool is_palindrome(u num, u k) {
    u l = 0, r = k - 1;
    while (l < r){
        char left = (1 & (num >> l)) ? 'A' : 'B';
        char right = (1 & (num >> r)) ? 'A' : 'B';
        if(left !=  right){
            return false;
        }
        r--; l++;
    }
    return true;
}

// Função para inicializar a lista de não-palíndromos
vector<u> generate_not_palindrome(u k) {
    vector<u> not_palindrome;
    for (u i = 0; i < (1U << k); ++i) {
        if (!is_palindrome(i, k)) {
            not_palindrome.emplace_back(i);
        } // else {
        //     cout << "Palindromo: ";
        //     for(int j = k - 1; j >= 0; j--)
        //         cout << ((i & (1 << j)) ? 'A' : 'B');
        //     cout << endl;
        // }
    }
    return not_palindrome;
}

// Função para inicializar a dp com base na string s
void initialize_dp(vector<u>& dp, const string& s, u k) {
    u a_mask = 0, q_mask = 0;
    for (u i = 0; i < k - 1; ++i) {
        a_mask = (a_mask * 2) + (s[i] == 'A');
        q_mask = (q_mask * 2) + (s[i] != '?');
        // cout << "q_mask = " << q_mask << endl;
    }
    for (u i = q_mask; i < (1U << (k - 1)); ++i) {
        if ((i & q_mask) == q_mask) {
            dp[i ^ a_mask] = 1;
        }
    }
}

void solve() {
    u n, k;
    cin >> n >> k;

    auto not_palindrome = generate_not_palindrome(k);
    string s;
    cin >> s;

    vector<u> dp(1U << (k - 1), 0), prev(1U << (k - 1), 0);
    initialize_dp(dp, s, k);

    for(auto i : dp){
        cout << i << " ";
    }
    cout << endl;

    const u mask = (1U << (k - 1)) - 1;
    for (u idx = k - 1; idx < s.size(); ++idx) {
        swap(dp, prev);
        fill(dp.begin(), dp.end(), 0);
        if (s[idx] != 'B') {
            for (const auto i : not_palindrome) {
                if (!(i & 1)) {
                    dp[i & mask] = (dp[i & mask] + prev[i / 2]) % MOD;
                }
            }
        }
        if (s[idx] != 'A') {
            for (const auto i : not_palindrome) {
                if (i & 1) {
                    dp[i & mask] = (dp[i & mask] + prev[i / 2]) % MOD;
                }
            }
        }
    }
    u result = 0;
    for (const auto val : dp) {
        result = (result + val) % MOD;
    }
    cout << result << endl;
}

int main() {
    solve();
    return 0;
}