P4965 薇尔莉特的打字机

题目背景

只要客人有意向，不论身在何处，都能上门服务。我是自动手记人偶服务——薇尔莉特·伊芙加登。

题目描述

薇尔莉特的打字机用了太久，按键已经开始老化了，因此有时候按键会没有反应。而薇尔莉特总是盲打，因此按键没反应她也不会注意到。一天，她用这台打字机继续完成一封还没写完的信。

现在告诉你这封信已经写好的部分以及薇尔莉特想进行的操作，薇尔莉特想进行的操作有两种：

在信的末尾输入一个大写字母

进行一次退格

退格用小写字母

薇尔莉特会按顺序按下她想按的按键，而每次薇尔莉特按下一个键（输入一个大写字母或进行一次退格），都有可能没有反应（即这次操作无效）。请问，最后打出来的信有多少种可能呢？（空信也算信）

当然薇尔莉特只想知道可能数对 0x125E591（十六进制）取模的结果。

输入输出格式

输入格式：

第一行两个正整数

第二行一个长度为

第三行一个长度为

输出格式：

一个整数表示答案对 0x125E591 取模的结果。

输入输出样例
输入样例#1：复制
2 4
AB
AuAB
输出样例#1：复制
9
输入样例#2：复制
10 5
AABBAACBAC
ABAAC
输出样例#2：复制
20
输入样例#3：复制
1 3
U
uUu
输出样例#3：复制
3
说明

$10^61≤n, m≤5×106$

样例解释

样例一：可能的

样例二：~~太多了，略~~。

样例三：可能的

~~这题的模数为什么这么奇怪应该不用我解释了~~

注：在本文中序列加法定义为拼接两个序列成一个序列。如： ${A,B}+{C}={A,B,C}$

思路
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 const int maxn=1e7+10;
 9 const int mod=0x125E591;
10 
11 char s[maxn],t[maxn];
12 int n,m,list[300],pre[maxn],pos,cnt,dp[maxn],ans;
13 int DP(char x)
14 {
15     if(list[x])
16     {
17         return mod-dp[pre[list[x]]];
18     }
19     else
20     return 1;
21 }
22 int tot=0;
23 
24 int main()
25 {
26     memset(dp,0,sizeof(dp));
27     int i;
28     cin>>n>>m; 
29     scanf("%s%s",s,t);
30     for (i=0;i<m;++i)
31     {
32         if(t[i]=='u')
33         {
34             tot++;
35         }
36     }
37     //cout<<cnt<<endl<<tot<<endl;
38     for (i=m-1;i>=0;--i)
39     {
40         if (t[i]!='u')
41         {
42             pre[i]=pos;
43             dp[i]=(2*dp[pos]+DP(t[i]))%mod;
44             pos=list[t[i]]=i;
45         }
46         else
47         {
48             if (n-tot>=0) 
49             {
50                 ans=(ans+dp[pos]+DP(s[n-tot]))%mod;
51             }
52             --tot;
53         }
54     }
55     ans=(ans+dp[pos]+1)%mod;
56     cout<<ans<<endl;
57     return 0;
58 }