前言
最慢的点才跑 \(2\) ms 的题解确定不看一看?
题意简述
给定长度为 \(n\) 的字符串 \(s\),其中 \(s_i \in \Omega\),求有多少子序列 \(T\) 满足任意 \(x \in \Omega\),其在 \(T\) 出现的位置为连续一段,当然,对 \(998244353\) 取模。
\(n \leq 10^5\),\(|\Omega| \leq 14\),时间 \(1\) 秒,空间 \(5\) MB。
(嗯……其实原题 \(n \leq 10^3\),\(|\Omega| \leq 10\),时间 \(2\) 秒,空间 \(1\) GB。)
题目分析
一眼状压 DP。因为我们需要知道之前选过的字符集合,以及当前上一位选出来的字符是什么。所以我们考虑记 \(f_{i, \mathcal{S}}\) 表示考虑前 \(i\) 位,必选 \(i\),选出的字符集合为 \(\mathcal{S}\) 的方案数。注意区分集合 \(\mathcal{S}\) 和字符串 \(s\)。有如下两种转移:
-
当前字符是子序列第一位:
直接 \(f_{i, \lbrace s_i \rbrace} = 1\)。 -
当前字符不是子序列第一位:
\[f_{i, \mathcal{S} \cup \lbrace s_i \rbrace} \gets f_{i, \mathcal{S} \cup \lbrace s_i \rbrace} + \begin{cases} f_{j, \mathcal{S}} & \text{ if } s_i = s_j \\ f_{j, \mathcal{S}} & \text{ if } s_i \neq s_j \land s_i \not \in \mathcal{S} \\ 0 & \text{ otherwise } \end{cases} \]
那么肯定是从 \(j \in [1, i - 1]\) 拼接来的。枚举 \(j\) 处选出的字符集合 \(\mathcal{S}\),根据上一次选出的最后一位 \(s_j\),结合题目要求有如下转移:解释一下吧,第一种情况是直接接在 \(j\) 之后,第二种情况是新开一段。
答案就是 \(\sum \limits _ {i = 1} ^ n \sum \limits _ {\mathcal{S} \subseteq \Omega} f_{i, \mathcal{S}}\)。
这样,时间复杂度是 \(\Theta(n ^ 2 2 ^ {|\Omega|})\),菜爆了,无论时空都不优秀。优化思路是先把 \(\Theta(n)\) 地枚举 \(j\) 优化掉。自然想到可以滚一滚,删除 \(i\) 这一维,但是这样我们不好判断上一次选出来的字符是什么,所以再加上一维 \(k\) 表示上一次选出来的是哪一种字符。
类似 01 背包,我们每次需要让 \(\mathcal{S}\) 从 \(\Omega \rightarrow \varnothing\),即代码实现上的从大到小枚举。类似得到转移方程。对于每一个包含 \(s_i\) 的 \(\mathcal{S}\),计算 \(f_{\mathcal{S}, s_i}\)。
- \(f_{\mathcal{S}, s_i} \gets f_{\mathcal{S}, s_i} + f_{\mathcal{S}, s_i}\):
表示选出 \(s_i\),有 \(f_{\mathcal{S}, s_i}\) 种方案,又由于 \(f\) 被滚了,是类似前缀和的操作,所以累加上去。 - \(f_{\mathcal{S}, s_i} \gets f_{\mathcal{S}, s_i} + f_{\mathcal{S} \setminus \lbrace s_i \rbrace, k}\):
表示新开一段,其中 \(k \in \mathcal{S} \setminus \lbrace s_i \rbrace\)。
注意到,我们还有把当前字符选出来成为第一位这一操作,由于滚动数组,我们不能再上述操作前修改,而是再上述操作后使 \(f_{\lbrace s_i \rbrace, s_i} \gets f_{\lbrace s_i \rbrace, s_i} + 1\)。
统计答案显然是 \(\sum \limits _ {\mathcal{S} \subseteq \Omega} \sum \limits _ {i \in \mathcal{S}} f_{\mathcal{S}, i}\)。
时间复杂度优化到 \(\Theta(n |\Omega| 2^{|\Omega}|)\),还是不够。
发现瓶颈在枚举 \(k\) 的过程中。我们发现对于 \(k \not \in \mathcal{S} \setminus \lbrace s_i \rbrace\) 的情况,由于 \(f_{\mathcal{S} \setminus \lbrace s_i \rbrace, k} = 0\),并不会对答案产生影响。所以等价于求 \(\sum \limits _ {k \in \Omega} f_{\mathcal{S} \setminus \lbrace s_i \rbrace, k}\)。所以,我们同时维护 \(g_{\mathcal{S}}\) 表示 \(\sum \limits _ {k \in \Omega} f_{\mathcal{S}, k}\) 就能快速转移了。
答案便是 \(\sum \limits _ {\mathcal{S} \subseteq \Omega} g_{\mathcal{S}}\)。
时间复杂度 \(\Theta(n 2 ^ {|\Omega|})\),就差一点点了,似乎差一个 \(\cfrac{1}{2}\) 的常数,上哪找去呢?
发现,枚举对于每一个包含 \(s_i\) 的 \(\mathcal{S}\) 是 \(\Theta(n)\) 的,但是我们完全可以只枚举 \(\mathcal{T} \in \Omega \setminus \lbrace s_i \rbrace\),而 \(\mathcal{S} = \mathcal{T} \cup \lbrace s_i \rbrace\),这样就有了一个 \(\cfrac{1}{2}\) 的常数,能够通过。
当然,聪明的读者肯定会发现,空间也可以有一个 \(\cfrac{1}{2}\) 的常数,因为只有对于 \(k \in \mathcal{S}\) 的 \(f_{\mathcal{S}, k}\) 才是有效的,程序二进制上,我们可以扣掉 \(\mathcal{S}\) 在 \(k\) 位的 \(1\),然后把之后的比特位向前挪动一格,这样就能节约空间,但是会带来性能上的额外消耗。
代码
#include <cstdio>
using namespace std;
using mint = int;
using sint = long long;
constexpr const mint mod = 998244353;
constexpr inline mint add(const mint a, const mint b) {
return a + b >= mod ? a + b - mod : a + b;
}
template <typename... Types>
inline mint& toadd(mint &a, Types... b) {
return a = add(a, b...);
}
const int N = 1010, M = 10;
int n, val[N];
char str[N];
mint dp[1 << M][M], g[1 << M];
signed main() {
scanf("%d%s", &n, str + 1);
for (int i = 1; i <= n; ++i) val[i] = str[i] - 'A';
dp[1 << val[1]][val[1]] = 1;
g[1 << val[1]] = 1;
for (int i = 2; i <= n; ++i) {
int ST = ((1 << M) - 1) ^ 1 << val[i];
for (int S = ST; ; S = (S - 1) & ST) {
int st = S | 1 << val[i];
toadd(g[st], dp[st][val[i]]);
toadd(g[st], g[st ^ 1 << val[i]]);
toadd(dp[st][val[i]], dp[st][val[i]]);
toadd(dp[st][val[i]], g[st ^ 1 << val[i]]);
if (!S) break;
}
toadd(dp[1 << val[i]][val[i]], 1);
toadd(g[1 << val[i]], 1);
}
mint ans = 0;
for (int st = 0; st < 1 << M; ++st)
toadd(ans, g[st]);
printf("%d", ans);
return 0;
}
后记
一道大水题,但是完全可以优化,别的题解都太劣了。以及本来想申请撤下一篇题解的,但是发现他已经被禁用专栏了,乐。就不直接说是谁了,给读者引用一坨原文吧:
一道合适的 DP 题。
考虑枚举,但是 balabala \(2\)s 时限不够。
自然的想到 DP,状态转移方程式:
\[dp[i][u][j] = dp[i - 1][u][j] \]\(i \in [1, n], u \in [0, 1023], j \in [0, 9]\)
剩下的就是加,赋值,取模,输出。
balabala 省略了其列举了数据范围,不知所云的计算。先不说错别字、中括号用得标不标准、状压集合表示得规不规范,就凭只有一句和题解搭得上边的话:“剩下的就是加,赋值,取模,输出”,就足以令人作呕了。
那篇题解的作者如果认为我侵犯到您了,可以联系我删除这一段,我并不是恶意引战。
希望我的题解能给大家带来启示和帮助。
标签:lbrace,rbrace,Chain,题解,mint,Contestant,mathcal,Omega From: https://www.cnblogs.com/XuYueming/p/18374856