题意：给你两个串，求用m个R，n个D能组成多少个包含这两个串
题解：先构造一个AC自动机记录每个状态包含两个串的状态，
状态很容易定义 dp【i】【j】【k】【status】表示在AC自动机K这个节点
使用了 i 个D,j个R ，状态为status的方案数。
然后直接DP即可。
1 #include <set> 2 #include <map> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstring> 11 #include <iostream> 12 #include <algorithm> 13 #include <unordered_map> 14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("****** ") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<<x<<endl 25 #define sfi(a) scanf("%d", &a) 26 #define sffi(a, b) scanf("%d %d", &a, &b) 27 #define sfffi(a, b, c) scanf("%d %d %d", &a, &b, &c) 28 #define sffffi(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d) 29 #define sfL(a) scanf("%lld", &a) 30 #define sffL(a, b) scanf("%lld %lld", &a, &b) 31 #define sfffL(a, b, c) scanf("%lld %lld %lld", &a, &b, &c) 32 #define sffffL(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d) 33 #define sfs(a) scanf("%s", a) 34 #define sffs(a, b) scanf("%s %s", a, b) 35 #define sfffs(a, b, c) scanf("%s %s %s", a, b, c) 36 #define sffffs(a, b, c, d) scanf("%s %s %s %s", a, b,c, d) 37 #define FIN freopen("../in.txt","r",stdin) 38 #define gcd(a, b) __gcd(a,b) 39 #define lowbit(x) x&-x 40 #define IO iOS::sync_with_stdio(false) 41 42 43 using namespace std; 44 typedef long long LL; 45 typedef unsigned long long ULL; 46 const ULL seed = 13331; 47 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL; 48 const int maxn = 1e6 + 7; 49 const int maxm = 8e6 + 10; 50 const int INF = 0x3f3f3f3f; 51 const int mod = 1e9 + 7; 52 int T, m, n; 53 char buf[1005]; 54 int dp[105][105][205][4]; 55 56 int get_num(char ch) { 57 if (ch == 'D') return 0; 58 else return 1; 59 } 60 61 struct Aho_Corasick { 62 int next[210][2], fail[210], End[210]; 63 int root, cnt; 64 65 int newnode() { 66 for (int i = 0; i < 2; i++) next[cnt][i] = -1; 67 End[cnt++] = 0; 68 return cnt - 1; 69 } 70 71 void init() { 72 cnt = 0; 73 root = newnode(); 74 } 75 76 void insert(char buf[], int id) { 77 int len = strlen(buf); 78 int now = root; 79 for (int i = 0; i < len; i++) { 80 if (next[now][get_num(buf[i])] == -1) next[now][get_num(buf[i])] = newnode(); 81 now = next[now][get_num(buf[i])]; 82 } 83 End[now] |= (1 << id); 84 } 85 86 void build() { 87 queue<int> Q; 88 fail[root] = root; 89 for (int i = 0; i < 2; i++) 90 if (next[root][i] == -1) next[root][i] = root; 91 else { 92 fail[next[root][i]] = root; 93 Q.push(next[root][i]); 94 } 95 while (!Q.empty()) { 96 int now = Q.front(); 97 Q.pop(); 98 End[now] |= End[fail[now]]; 99 for (int i = 0; i < 2; i++) 100 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 101 else { 102 fail[next[now][i]] = next[fail[now]][i]; 103 Q.push(next[now][i]); 104 } 105 } 106 } 107 108 LL solve() { 109 mem(dp, 0); 110 dp[0][0][0][0] = 1; 111 for (int i = 0; i <= n; ++i) { 112 for (int j = 0; j <= m; ++j) { 113 for (int k = 0; k < cnt; ++k) { 114 for (int status = 0; status < 4; ++status) { 115 if (dp[i][j][k][status] == 0) continue; 116 for (int l = 0; l < 2; ++l) { 117 int idx = next[k][l]; 118 if (l == 0) { 119 dp[i + 1][j][idx][status | End[idx]] = 120 (1LL * dp[i + 1][j][idx][status | (End[idx])] + 1LL * dp[i][j][k][status]) % 121 mod; 122 // printf("i = %d j = %d idx = %d status = %d dp = %lld ", i + 1, j, idx, 123 // status | (End[idx]), 124 // dp[i + 1][j][idx][status | End[idx]]); 125 } else { 126 dp[i][j + 1][idx][status | End[idx]] = 127 (1LL * dp[i][j + 1][idx][status | End[idx]] + 1LL * dp[i][j][k][status]) % mod; 128 // printf("i = %d j = %d idx = %d status = %d dp = %lld ", i, j + 1, idx, 129 // status | (End[idx]), 130 // dp[i][j + 1][idx][status | End[idx]]); 131 } 132 } 133 } 134 } 135 } 136 } 137 LL ans = 0; 138 for (int i = 0; i < cnt; ++i) ans = (ans + dp[n][m][i][3]) % mod; 139 return ans; 140 } 141 142 void debug() { 143 for (int i = 0; i < cnt; i++) { 144 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]); 145 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]); 146 printf("] "); 147 } 148 } 149 } ac; 150 151 int main() { 152 // FIN; 153 sfi(T); 154 while (T--) { 155 sffi(m, n); 156 ac.init(); 157 for (int i = 0; i < 2; ++i) { 158 sfs(buf); 159 ac.insert(buf, i); 160 } 161 ac.build(); 162 printf("%lld ", ac.solve()); 163 } 164 return 0; 165 }