一道很好的锻炼推式子能力的题，也是本蒟蒻第一道一遍过的紫题。
既然是递推，那就先定义一下状态： 表示在执行完第 个操作后，可能得到的字符串数量。
很明显，我们需要分两种情况讨论：这次操作为添加字符或退格。
先分析第一种情况，添加字符。这个时候又要分两种小情况：
当这个字符在操作中是第一次出现时，把它接在任何已有的字符串后面，都不会重复。所以 ；
当这个字符在操作中已经出现过时，设它上次出现处为 ，通过手模很容易发现，在这种情况下会出现重复，而重复的次数则是 ，因为如果从 到 的操作都没执行出来，再将第 次操作的字符接在后面，就相当于是接第 次操作的字符在后面，而这种情况又是已经计算过的。所以 。
第二种情况，退格。我们会发现，得到的全部都是重复的字符串，只有一种情况除外：此前的操作，所有添加字符都没执行，所有退格都有执行，这个时候就会多出一种情况：原有的字符串去掉末尾长度为 的字串后剩下的字符串， 为在该操作之前出现过的退格操作数。只要 ，就会同上所述，多出一个新的字符串。。反之就不会，。
还需要注意的是，举个例子，原有字符串为 AB，操作uB。这个时候答案不是 ，而是。为什么呢？因为多算了删去 B 又添加 B 的情况，还要额外再减 。所以我们不妨设 为下一次出现 字符时，要减去的情况数，当前字符为 。那么全部的递推式就是：
还有一处值得一提：本人第一次写的时候，当有添加字符的操作时，把之前所有出现过的字符所产生的重复都算上了，然后就很容易地没过样例。想了一下，是因为前一个相同字符之前所产生的影响都包含在了其中，所以不用统计。
code：
int n,m,cnt[27],f[maxn];
char s[maxn],t[maxn];
void solve(){
scanf("%d%d%s%s",&n,&m,s+1,t+1);
f[0]=1;//别忘了初始化
for(int i=1,k=0;i<=m;i++){
if(t[i]=='u'){
if(k<n)f[i]=f[i-1]+1;
else f[i]=f[i-1];
if(k<n)cnt[s[n-k]-'A'+1]++;
k++;
}else{
int x=t[i]-'A'+1;
f[i]=f[i-1]*2%mod;
f[i]=(f[i]-cnt[x]+mod)%mod;
cnt[x]=f[i-1];
}
}
printf("%d",f[m]);
}
