【PGBattle2023】ましゅまろ 難易度5 : ダンス

[Q] https://products.sint.co.jp/hubfs/resource/topsic/pgb2023/1_4.pdf

考察
1. 区間DPで考える。
2. DP[0][N]が答え。
3. 区間の幅を2,4,6,8,…と固定し、徐々に増やして探索。
4. 固定幅の中で、FMのペアを全探索。開始地点を固定する。
5. FM区間と、その外側の区間でDPの積とcombinationの積をとる。

幅8のとき

FMBBBBBB // DP[0][8] += DP[1][1] * DP[2][8] * COM(4, 1)
FAAMBBBB // DP[0][8] += DP[1][3] * DP[4][8] * COM(4, 2)
FAAAAMBB // DP[0][8] += DP[1][5] * DP[6][8] * COM(4, 3)
FAAAAAAM // DP[0][8] += DP[1][7] * DP[8][8] * COM(4, 4)

の4通りで検証。
(Aの取り方のDP) * (Bの取り方のDP) * combination

combinationは、(FM+A)とBの取り方が独立になっているので、処理回数のCOMを求める。

実装

mint DP[101][101];
int main() {
  MOD = 998244353;
  COMinit();
  cincout();
  ll N;
  string S;
  cin >> N >> S;

  if (N % 2 == 1){
    cout << 0 << endl;
    return 0;
  }

  rep(i, N + 1) DP[i][i] = 1;
  for(ll r = 2; r <= N; r += 2){ // 幅を固定[s, s+r) DP[s][s+r]を求める
    rep(s, N - r + 1){ // 開始地点を固定
      for(ll t = s + 2; t <= s + r; t += 2){ // FMのペアを固定
        if (S[s] == S[t - 1]) continue;
        // FAAAAMBB FMが(s,t-1)で、DP[s+1][t-1]がA, DP[t][s+r]がB。　COM(all/2, (A+FM)/2)
        DP[s][s + r] += DP[s + 1][t - 1] * DP[t][s + r] * COM(r / 2, (t - s) / 2);
      }
    }
  }

  auto debug=[&](){
    rep(i, N + 1) rep(j, N + 1){
      if (DP[i][j] == 0) continue;
      cerr << "DP[" << i << "][" << j << "] = " << DP[i][j] << endl;
    }
  };
  // debug();
  cout << DP[0][N] << endl;
}

提出テストはできない。よわよわサンプルは通っているだけのコードなので、確証はない。