被同机房神犇使用一顿晚饭的时间爆切并当成作业布置给我的题...
虽然是紫，但实际难度处于可以接受的范围内。
题目分析
开始的思路是 \(\text{set}\) 乱搞，因为发现对于每一次操作，如果执行那么一定会对前面的字符串有影响，所以直接放进 \(\text{set}\) 判重，最后输出元素个数即可。
但是这样要记录上一次处理时的状态，实现起来会很怪，而且复杂度似乎不是很对，所以最后就放弃了。
但是有刚刚的尝试，不难想到正解：动态规划。
在定义状态方面，我原来选择的是二维，用 \(dp_{i,0}\) 表示不选择第 \(i\) 个操作，\(dp_{i,1}\) 表示选择，看它们可能得到的字符串数量。
但是后来发现可以直接压一维，直接用 \(dp_i\) 就可以了。
由于删除操作明显异于加入任何一个字符，所以进行分类讨论。
- 添加字符
- 新添加的字符没有被出现过
这种情况下不会出现与之前重复的字符串，所以直接乘就可以了。
\[dp_i = dp_{i-1} \times 2 \]- 新添加的字符已经出现过
开始没有专门考虑这种情况，而是想办法用其他东西，比如刚刚提到的 \(\text{set}\) 判重。
但是这个东西可以直接放到状态转移方程里面。
我们考虑记录每一个字符最后出现的位置，记为 \(des\)。那么可以推出，需要去的重复个数就是 \(dp_{des - 1}\)。
为什么？我也不知道
所以我去问了 @yinhee 神犇（也是作业布置者），搞明白了原理。由于这个字符已经出现过，所以在第 \(des\) 个操作出现时，第 \(des\) 到 \(i - 1\) 可以不执行，这样该字符串的末尾并不会改变。所以这一部分是需要去掉的，即可得出：
\[dp_i = dp_{i-1} - dp_{des-1} \]- 删除字符
- 此前执行过添加字符
此时无论干什么，求出的都一定是重复的情况，不用记录。
\[dp_i = dp_{i-1} \]- 此前没有执行过添加字符
如果我们操作了 \(x\) 次删除字符，如果 \(x \le n-1\) ，那么就可以得到一种新情况。
\[dp_i = dp_{i-1} + 1 \]- 特殊处理
这种其实最好想，即一个字符如果刚被删除就被加到了最后，这种情况没有被前面任何一种情况包括进去，单独处理即可。
贴上代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=19260817;
const int maxn=5000005;
int n,m,a[30];
int cnt;
int dp[maxn];
string s,u;
inline void init(){
cin>>n>>m;
cin>>s>>u;s=" "+s;u=" "+u;
dp[0]=1;
}
signed main(){
init();
for(register int i=1;i<=m;++i){
if(u[i]=='u'){ //是删除
if(cnt<n){
dp[i]=dp[i-1]+1;
a[s[n-cnt]-'A'+1]++;
}
else dp[i]=dp[i-1];
cnt++;
}
else{ //不是
dp[i]=dp[i-1]*2%mod;
dp[i]=(dp[i]-a[u[i]-'A'+1]+mod)%mod;
a[u[i]-'A'+1]=dp[i-1];
}
}
cout<<dp[m]%mod;
}