AT_abc425_f [ABC425F] Inserting Process 题解

hjqhs · 2025-10-14 19:08:58 · 个人记录

已严肃复习状压 dp。
首先将正着加转换成倒着删，由于 n \le 22 故考虑状压。将每个字符是否满足最终状态状压。显然转移为所有子集。注意转移时要记住与上一次删的不能相等，因为 aa 删第一个 a 和删第二个 a 所形成的序列是一样的。

// Problem: Inserting Process
// Contest: Virtual Judge - AtCoder
// URL: https://vjudge.net/problem/AtCoder-abc426_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// Created Time: 2025-10-14 18:53:05
// Author: hjqhs
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
typedef long long ll;
typedef unsigned long long ull;
const int N = 23;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int n, f[1 << N];
string s;
void solve() {
    cin >> n >> s; f[(1 << n) - 1] = 1;
    per(i, (1 << n) - 1, 0) {
        char lasc = ' ';
        rep(j, 0, n - 1) {
            if((i >> j) & 1) {
                if(s[j] != lasc) f[i ^ (1 << j)] = (f[i ^ (1 << j)] + f[i]) % MOD;
                lasc = s[j];
            }
        }
    }
    cout << f[0] << '\n';
    return;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while(T --) solve();
    return 0;
}