题目大概说有个n×m的格子，有两种走法，每种走法都是一个包含D或R的序列，D表示向下走R表示向右走。问从左上角走到右下角的走法有多少种走法包含那两种走法。
D要走n次，R要走m次，容易想到用AC自动机上的DP解决：
- 用两种走法的序列构造AC自动机
- dp[i][j][S][k]表示D用了i个R用了j个，且当前走到自动机的S结点，已经包含的走法的状态集合是k的方案数
- 转移就是走R或者走D了，我用我为人人来转移
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXN 222
int tn,ch[MAXN][],fail[MAXN],flag[MAXN];
int idx[];
void insert(char *s,int k){
int x=;
for(int i=; s[i]; ++i){
int y=idx[s[i]];
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
}
flag[x]|=(<<k);
}
void getfail(){
memset(fail,,sizeof(fail));
queue<int> que;
for(int i=; i<; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int x=que.front(); que.pop();
for(int i=; i<; ++i){
if(ch[x][i]){
que.push(ch[x][i]);
fail[ch[x][i]]=ch[fail[x]][i];
flag[ch[x][i]]|=flag[ch[fail[x]][i]];
}else ch[x][i]=ch[fail[x]][i];
}
}
} int d[][][MAXN][]; int main(){
idx['R']=; idx['D']=;
int t,n,m;
char str[];
scanf("%d",&t);
while(t--){
tn=;
memset(ch,,sizeof(ch));
memset(flag,,sizeof(flag));
scanf("%d%d",&n,&m);
for(int i=; i<; ++i){
scanf("%s",str);
insert(str,i);
}
getfail();
memset(d,,sizeof(d));
d[][][][]=;
for(int len=; len<n+m; ++len){
for(int i=; i<=len; ++i){
int j=len-i;
if(j>m || i>n) continue;
for(int s=; s<=tn; ++s){
for(int k=; k<; ++k){
d[i+][j][ch[s][]][k|flag[ch[s][]]]+=d[i][j][s][k];
d[i+][j][ch[s][]][k|flag[ch[s][]]]%=;
d[i][j+][ch[s][]][k|flag[ch[s][]]]+=d[i][j][s][k];
d[i][j+][ch[s][]][k|flag[ch[s][]]]%=;
}
}
}
}
int res=;
for(int i=; i<=tn; ++i){
res+=d[n][m][i][];
res%=;
}
printf("%d\n",res);
}
return ;
}