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

· · 题解

题目传送门

考虑到可能出现的字符串不止一个，我们建立一棵字典树，将字典树上的节点看作一个串。

如果这个串可能出现，则把它涂黑。

因为每次操作都可以不按，所以第i-1次操作后的黑色节点在第i次操作后仍然是黑色。

如果按下，则会有新的黑色节点产生。

所以这是一个不断扩展的过程。

为了方便，我们暂时不考虑u。

假设我们现在进行第i次操作，字母为s[i]。

每个黑色节点的第s[i]个儿子都可以被涂黑。

那么现在的黑色节点的数量是原先的两倍吗？

显然不是。

（为了方便，假设只有三种不同的字母）

如上图所示，0和1已经变为黑节点。若再按下a,则0->1,1->2

发现1号节点重复出现。

因此，我们需要一个数组，F[i]表示当前状态下有多少黑色节点已经有第i个儿子，转移时应减去它们产生的节点。

因此，第i次黑色节点=第(i-1)次黑色节点 * 2 - F[s[i]]。

现在问题就转化为了如何不断更新F[i]。

假如现在执行第i次操作

所有黑色节点跳到第s[i]个儿子的位置。

那么，所有原来的黑色节点都拥有第s[i]个儿子，因此，F[s[i]]更新为第i-1次操作后的黑色节点数量。

而对于其他的字符j，所有黑色节点中有第j个儿子的节点数量并没有发生变化，不需要更新。

就这样愉快地解决了吗？

我们还要考虑退格的情况。

如果一个字符串先在末尾加了一个字符，然后又删掉了，相当于一直没有变化。

所以，我们只需要考虑真实操作串都是u的串。这其实是在字典树中不断往上跳的过程。

所以，我们每遇到一个u,直接把答案+1就可以了。

但是，如果当前串已经删成空串了，就可以直接跳过这个过程。

那么F数组如何更新呢？

我们考虑统计到目前为止u的总个数cnt,那么现在删掉的是第1个串中的第(n-cnt+1)个字符。

对于这个字符s,我们只需要将F[s]++即可。

时间复杂度O(n)。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#define mod 19260817 //一个神秘的模数
#define M 10000005
using namespace std;
int n,m,cnt;//cnt表示当前删的位置
char A[M],B[M];
long long ans=1,F[30];
int main(){
    scanf("%d%d%s%s",&n,&m,A+1,B+1);cnt=n;//读入
    for (int i=1;i<=m;i++)
        if (B[i]>='A'&&B[i]<='Z'){
            long long tmp=F[B[i]-'A'+1];
            F[B[i]-'A'+1]=ans;//更新F数组
            ans=((ans+ans-tmp)%mod+mod)%mod;//更新ans
        }
        else {
            if (!cnt) continue;//如果当前串删完了就跳过
            F[A[cnt]-'A'+1]=(F[A[cnt]-'A'+1]+1)%mod;//更新F数组
            ans=(ans+1)%mod;cnt--;//更新ans
        }
    printf("%lld",ans);
    return 0;
}