Submission #69714922

---

Source Code Expand

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

constexpr int mod = 998244353;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n;
  string t;
  cin >> n >> t;

  //////////////// 出力変数定義 ////////////////

  int result = 0;

  //////////////////// 処理 ////////////////////

  // DPテーブル
  // bitが立っている位置の文字だけ拾ったやつが、何パターンで作れるか
  vector<int> dp(1<<n,0);

  // 空文字列は1としておく
  dp.at(0) = 1;

  // 空以外の文字列を埋めていく
  for (int i=1; i<(1<<n); i++) {

    // 1つ前で抜いた文字
    char c = '*';

    // ビットが立っているところを順に見る
    for (int j=0; j<n; j++) {

      // ビットが立っているところで、直前と文字被りでなかったら、そのパターン数を足してcを更新
      if (i&(1<<j)&&t.at(j)!=c) {
        dp.at(i) += dp.at(i-(i&(1<<j)));
        dp.at(i) %= mod;
        c = t.at(j);
      }
    }

  }

  // テーブルの最後が答え
  result = dp.back();

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result