题解：AT_abc425_f [ABC425F] Inserting Process

jackzhangcn2013 · 2025-10-01 15:27:43 · 题解

解法

考虑状压 DP。

首先，如果一个一个添字符是很难做的，那我们可以反着来，考虑一个一个删字符。

设 f_{S} 表示已经删除了的字符集合为 S，总共有多少种可能的删除方法。

对于每个 f_{S}，很明显他能对所有比 S 多删了一个字符的 f_{T} 造成贡献，可以 O(n) 枚举，所以总时间复杂度为 O(n2^n)。

但你以为这样就结束了吗？不，如果你尝试运行样例，你就会发现答案比正确答案多了一点。

为什么呢？我们可以发现，有些删除字符的操作序列看起来是一样的。比如有字符串 aabb，先删第 1 位和先删第 2 位是一样的。为了解决这种情况，我们规定如果当前字符串有多个字符相同，那么就必须从最左边开始删，这样问题就解决了。

代码

#include <bits/stdc++.h>
#define int long long
const int N = 25;
const int Mod = 998244353;
using namespace std;
int n;
string t;
int f[1 << N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> t;
    f[0] = 1;
    for (int S = 0; S < 1 << n; S++)
    {
        int pre = -1;
        for (int i = 0; i < n; i++)
        {
            if (S & (1 << i))
            {
                continue;
            }
            if (pre == -1 || t[i] != t[pre])
            {
                int T = S | (1 << i);
                f[T] += f[S];
                f[T] %= Mod;
            }
            pre = i;
        }
    }
    cout << f[(1 << n) - 1];
    return 0;
}