提出 #54838113

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;


using ll = long long;

int N, K;
string S;
const ll mod = 998244353;

map<int, map<string, ll>> dp;
bool isPal(string& t) {
  int L = 0, R = t.length() - 1;
  while(L < R) {
    if(t[L] != t[R]) return 0;
    L++;
    R--;
  }
  return 1;
}
ll f(int i, string t) {
  if(i >= N) {
    if(isPal(t)) return 0;
    return 1;
  }

  if(dp.find(i) != dp.end() && dp[i].find(t) != dp[i].end()) {
    return dp[i][t];
  }

  if(i >= K && isPal(t)) {
    return dp[i][t] = 0;
  }


  ll ans = 0;
  if(S[i] == '?') {
    S[i] = 'A';
    ans = (ans + f(i + 1, S.substr(max(0, i - K + 1), min(i + 1, K)))) % mod;
    S[i] = 'B';
    ans = (ans + f(i + 1, S.substr(max(0, i - K + 1), min(i + 1, K)))) % mod;
    S[i] = '?';
  } else {
    ans = (ans + f(i + 1, S.substr(max(0, i - K + 1), min(i + 1, K)))) % mod;
  }
  return dp[i][t] = ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> K;
  cin >> S;
  string t = "";
  cout << f(0, t) << endl;
  return 0;
}

提出情報

ジャッジ結果