题解 P4965 【薇尔莉特的打字机】

~~这题的模数为什么这么奇怪应该不用我解释了~~ > 注：在本文中序列加法定义为拼接两个序列成一个序列。如：$\{A,B\}+\{C\}=\{A,B,C\}$ ### 一、 首先考虑没有退格的情况，等同于求一个序列的本质不同子序列个数。 把子串 $t_{0..i}$ 看作一个序列，用 $\widetilde{t_{0..i}}$ 代指其所有本质不同的**非空**子序列， $f_i$ 表示其本质不同的非空子序列的总个数。为得到 $f_i$，考虑线性 $dp$ 转移。 在递推过程中，如果 $t_i$ 表示的字母第一次出现，即 $t_{0..i-1}$ 中没有字符与 $t_i$ 相同。此时 $\widetilde{t_{0..i}}$ 分 $3$ 类： - $1.\ \widetilde{t_{0..i-1}}$，共有 $f_{i-1}$ 个。 - $2.\ \widetilde{t_{0..i-1}} + \{t_i\}$，仍有 $f_{i-1}$ 个。 - $3.\ \widetilde{t_{0..i-1}}$ 不包含空序列，所以第 $2$ 类中不包含 $\{t_i\}$，单独讨论，共有 $1$ 个。 综上所述，若 $t_i$ 第一次出现，$f_i = 2f_{i-1} + 1$。 那万一 $t_i$ 不是第一次出现呢？按照上面的讨论，必定会产生重复的答案。 令 $lst[x]$ 表示字符 $x$ 上一次出现的位置。$\widetilde{t_{0..lst[t_i] - 1}} + \{t_{lst[t_i]}\}$ 与 $\widetilde{t_{0..lst[t_i] - 1}} + \{t_i\}$ 重复，$\{t_{lst[t_i]}\}$ 与 $\{t_i\}$ 重复。所以 $f_i$ 要减去 $f_{lst[t_i]-1}+1$。 为什么仅有这些子序列重复呢？因为重复的解必然以 $t_i$ 结尾，而 $f_{lst[t_i]-1}+1$ 已经包含了 $t_{0..lst[t_i]}$ 这个序列所有以 $t_i$ 结尾的本质不同子序列了（仔细想想就能明白为什么）。 总结一下转移方程： $f_i=\begin{cases}2f_{i-1}+1\quad(t_i\text{第一次出现})\\2f_{i-1}-f_{lst[t_i]-1}\quad (t_i\text{出现过})\end{cases}$ 只要 $O(m)$ 的时间复杂度便可实现以上递推。 ### 二、 接着考虑如何处理退格。 打出了一个字母但被之后的退格所删除，无异于打字操作与退格操作都没有进行。所以只用考虑 $\mathrm{u}$ 排在最开头的情况。 当有效的 $\mathrm{u}$ 一共有 $k$ 个时，只用考虑这 $k$ 个 $\mathrm{u}$ 为操作串 $t$ 从左往右数的前 $k$ 个 $\mathrm{u}$ ，这包含了所有答案。 以 $pre[i]$ 表示 $t_{i+1..m-1}$ 第一个不是 $\mathrm{u}$ 的位置。同时，**下文中本质不同的子序列一律不包含 $\mathrm{u}$**。 设第 $k$ 个 $\mathrm{u}$ 的位置为 $p_k$，退 $k$ 次格新增的本质不同子序列包括 $s_{0..n-k-1} + \widetilde{t_{pre[p_k]..m-1}}$，以及 $s_{0..n-k-1}$。我们把目光放到 $\widetilde{t_{pre[p_k]..m-1}}$ 上，如果对于每个 $k$ 都做一次顺推 $dp$，时间复杂度将会退化至 $O(m ^ 2)$。但是，右端点 $m-1$ 始终不变，把顺推转换为倒推即可。 所以，$f_i$ 的意义就变为 $\widetilde{t_{i..m-1}}$ 的总个数，$lst[x]$ 的意义就变为倒推时字符 $x$ 上一次出现的位置。此外，由于退格符 $\mathrm{u}$ 的存在，转移方程中的 $f_{i-1}$ 改为 $f_{pre[i]}$。 于是，我们得到了一个（错误）的算法： - 倒推，对于每个大写字母计算 $f_i$，对于每个 $\mathrm{u}$ 把答案加上 $f_{pre[p_k]}+1$（加一是因为 $f_{pre[p_k]..m-1}$ 不含 $s_{0..n-k-1}$），最后再加上 $f_{pre[0]}+1$ ( $pre[0]$ 表示 $t_{0..m-1}$ 中第一个非 $\mathrm{u}$ 的位置) 和第一部分类似，若退格所删去的最后一个字符即 $s_{n-k}$ 在 $t_{pre[p_k]..m-1}$ 中出现过，这个算法会产生重复的答案：第 $k$ 个 $\mathrm{u}$ 在原串 $s$ 中删除的字符是 $s_{n-k}$，而在做第 $k - 1$ 个 $\mathrm{u}$ 时，这个字符并不会被删除。想象一下，一旦 $s_{n-k}$ 在 $t_{pre[p_k]..m-1}$ 中出现过，就意味着可以把刚删除的 $s_{n-k}$ 的给打回去，这与做第 $k - 1$ 个 $\mathrm{u}$ 时的情形相同。所以重复计算的本质不同子序列为 $s_{0..n-k}+\widetilde{t_{pre[lst[s_{n-k}]]..m-1}}$ 以及 $s_{0..n-k}$，个数为 $f_{pre[lst[s_{n-k}]]}+1$，计算答案时要将这部分减去。 仅有这些重复的原因同第一部分所述。 需要注意的是，如果 $\mathrm{u}$ 的个数大于 $n$，要忽略最后面的一些 $\mathrm{u}$，只考虑前 $n$ 个。 ### 代码 题解写了一大堆..然而代码非常短。 ``` #include <iostream> #include <cstdio> using namespace std; const int N=5000010; const int M=0x125E591; int uniq(char x); //计算重复 char s[N],t[N]; int n,m,lst[300],pre[N],pos,cnt,f[N],ans; //pos记录当前扫到的最后一个非u的位置，cnt表示还没扫到的u的个数 int main() { int i; scanf("%d%d%s%s",&n,&m,s,t); for (i=0;i<m;++i) { cnt+=t[i]=='u'; } for (i=m-1;i>=0;--i) { if (t[i]!='u') { f[i]=(2*f[pre[i]=pos]+uniq(t[i]))%M; pos=lst[t[i]]=i; } else { if (n-cnt>=0) //如果u的个数大于n，要忽略最后面的一些u { ans=(ans+f[pos]+uniq(s[n-cnt]))%M; } --cnt; } } ans=(ans+f[pos]+1)%M; printf("%d",ans); return 0; } int uniq(char x) { return lst[x]?M-f[pre[lst[x]]]:1; //M-f[pre[lst[x]]]就是-f[pre[lst[x]]]，因为是在模意义下运算所以+M } ```