前言
萌萌 DP 题。
思路
题目就是在说从 \(a\) 里面按顺序掏出来一些字母，使得相同的字母都是相邻的（比如 AABBBBCD 可行，AAABBCAA 不行）。
看起来很不可做，突破口在于 \(\text{A} \sim \text{J}\) 一共只有 \(10\) 个字母，考虑状压。
设 \(dp_{i,s}\) 表示选第 \(i\) 个字母，当前选取的子集为 \(s\)（二进制状压），方案数。
直接刷表。对于子集 \(s\) 中的一个已选位 \(i\)，枚举 \(i < j \le n\)：
- 如果 \(a_i = a_j\)，说明可以将 \(s\) 扩充上 \(a_j\)，所以 \(dp_{j,s} \gets dp_{i,s}\)。
- 如果 \(a_j \ne a_j\)，分两种情况：
- \(a_j\) 已经在 \(s\) 里出现过。由于 \(a_i \ne a_j\)，所以 \(a_j\) 与它之前的伙伴并不相邻，不合法。
- \(a_j\) 并没有出现过。于是可以新开一个伙伴的组合，即 \(dp_{j, s \cap a_i} \gets dp_{i, s}\)。
初始化 \(dp_{i, \{a_i\}} = 1\)，答案即 \(\sum\limits_{} dp_{i, s}\)。
代码
时间复杂度 \(O(n^2 2^T)\)，\(T\) 是 \(a\) 出现的不同字母数。注意到代码里的两层枚举都有剪枝，所以实际跑起来飞快。
#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 998244353;
int dp[1005][(1 << 10) + 5]; //dp[i][j] : 当前选第 i 个字母，选取子集为 j，方案数
int main()
{
int n; string a;
cin >> n >> a;
for (char &x : a) x -= 'a';
a = '%' + a;
for (int i = 1; i <= n; i++) dp[i][1 << a[i]] = 1;
for (int s = 0; s < (1 << 10); s++)
for (int i = 1; i <= n; i++)
if (s & (1 << a[i]))
for (int j = i + 1; j <= n; j++) {
if (a[i] == a[j]) (dp[j][s] += dp[i][s]) %= mod;
else if (!(s & (1 << a[j]))) (dp[j][s | (1 << a[j])] += dp[i][s]) %= mod;
}
int ans = 0;
for (int s = 0; s < (1 << 10); s++)
for (int i = 1; i <= n; i++)
ans = (ans + dp[i][s]) % mod;
cout << ans;
}
希望能帮助到大家！