AtCoder Beginner Contest 215E

ABC215E

BitDP. 今調べている \(i \in N\) に対して，コンテストに参加出来るかどうかは， 次の2つが分かっているれば十分．

• 今まで参加したことのあるコンテストの集合
• 最後に参加したコンテスト

実装:
10種類のコンテストがあるが， まだ 1回もコンテストに参加していない場合は，形式的に 11種類目のコンテストに参加したことにする．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  string s; cin >> s;

  ll T = 10;

  vector<vector<mint>> dp(1LL<<(T), vector<mint>(T+1));

  // dp[1LL<<T][T] = mint(1);

  dp[0][T] = 1;

  rep(i,n) {

    vector<vector<mint>> old(1LL<<(T), vector<mint>(T+1));

    swap(dp, old);

    // 形式的に x == T の場合を入れてあるから，

    // if(t >> x & 1) を入れると WA.

    rep(t, 1LL<<(T)) rep(x,(T+1)) { // if(t >> x & 1) : WA

      if(t && !(t >> x & 1)) continue; // この 1文は無くても AC

      ll y = s[i] - 'A';

      ll nt = t | (1LL << y);

      dp[t][x] += old[t][x];

     

      if(y == x) {

        dp[nt][y] += old[t][x];

      }else if(!(t >> y & 1)){

        dp[nt][y] += old[t][x];

      }    

     

    }

  }

  mint ans;

  rep(t, 1LL<<T) rep(x,T) if(t >> x & 1){

    ans += dp[t][x];

  }

  cout << ans.val() << endl;

  return 0;

}