Walk Through Squares
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1523 Accepted Submission(s): 507
Problem Description
On the beaming day of 60th anniversary of NJUST, as a military college which was Second Artillery Academy of Harbin Military Engineering Institute before, queue phalanx is a special landscape.
Here is a MN rectangle, and this one can be divided into MN squares which are of the same size. As shown in the figure below:
01—02—03—04
|| || || ||
05—06—07—08
|| || || ||
09—10—11—12
Consequently, we have (M+1)(N+1) nodes, which are all connected to their adjacent nodes. And actual queue phalanx will go along the edges.
The ID of the first node,the one in top-left corner,is 1. And the ID increases line by line first ,and then by column in turn ,as shown in the figure above.
For every node,there are two viable paths:
(1)go downward, indicated by ‘D’;
(2)go right, indicated by ‘R’;
The current mission is that, each queue phalanx has to walk from the left-top node No.1 to the right-bottom node whose id is (M+1)(N+1).
In order to make a more aesthetic marching, each queue phalanx has to conduct two necessary actions. Let’s define the action:
An action is started from a node to go for a specified travel mode.
So, two actions must show up in the way from 1 to (M+1)*(N+1).
For example, as to a 3*2 rectangle, figure below:
01—02—03—04
|| || || ||
05—06—07—08
|| || || ||
09—10—11—12
Assume that the two actions are (1)RRD (2)DDR
As a result , there is only one way : RRDDR. Briefly, you can not find another sequence containing these two strings at the same time.
If given the N, M and two actions, can you calculate the total ways of walking from node No.1 to the right-bottom node ?
Input
The first line contains a number T,(T is about 100, including 90 small test cases and 10 large ones) denoting the number of the test cases.
For each test cases,the first line contains two positive integers M and N(For large test cases,1<=M,N<=100, and for small ones 1<=M,N<=40). M denotes the row number and N denotes the column number.
The next two lines each contains a string which contains only ‘R’ and ‘D’. The length of string will not exceed 100. We ensure there are no empty strings and the two strings are different.
Output
For each test cases,print the answer MOD 1000000007 in one line.
Sample Input
2
3 2
RRD
DDR
3 2
R
D
Sample Output
1
10
题目链接：HDU 4758
题意就是让构造只含$\mathbf R$和$\mathbf D$的字符串，使得其只含$m$个$\mathbf R$和$n$个$\mathbf D$且题目给的两个字符串是其子串，求构造方案数。
首先肯定构造AC自动机，然后同时记得把fail的标记传递，记向$\mathbf R$走为$0$，向$\mathbf D$走为$1$，然后用$dp[u][j][k][s]$表示当前在AC自动机的第$u$个节点上，构造出的字符串含$j$个$\mathbf R$,$k$个$\mathbf D$，包含的字符串二进制状态为$s$，设$v$为$u$下一个可到达的节点，$l$为走的方向（向$\mathbf R$或$\mathbf D$走）那么可以发现：
这题枚举的顺序很重要，要在内层循环枚举所在节点，因为一个节点可能会被多次更新，一开始先枚举节点发现后面会漏算很多情况导致样例都出不来
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int mod = 1000000007;
const int N = 210;
struct Trie
{
int nxt[4];
int fail, cnt;
void init()
{
for (int i = 0; i < 4; ++i)
nxt[i] = -1;
fail = cnt = 0;
}
} L[N];
int sz;
int id[90];
int dp[N][105][105][4];
char str[N];
namespace AC
{
void init()
{
sz = 0;
L[sz++].init();
}
void ins(char s[], int len, int x)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
int v = id[(int)s[i]];
if (L[u].nxt[v] == -1)
{
L[sz].init();
L[u].nxt[v] = sz++;
}
u = L[u].nxt[v];
}
L[u].cnt |= (1 << x);
}
void build()
{
queue<int>Q;
L[0].fail = 0;
for (int i = 0; i < 2; ++i)
{
if (L[0].nxt[i] == -1)
L[0].nxt[i] = 0;
else
{
L[L[0].nxt[i]].fail = 0;
Q.push(L[0].nxt[i]);
}
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
int uf = L[u].fail;
if (L[uf].cnt)
L[u].cnt |= L[uf].cnt;
for (int i = 0; i < 2; ++i)
{
if (L[u].nxt[i] == -1)
L[u].nxt[i] = L[uf].nxt[i];
else
{
L[L[u].nxt[i]].fail = L[uf].nxt[i];
Q.push(L[u].nxt[i]);
}
}
}
}
}
int main(void)
{
int T, i, n, m, j, u, l, s;
scanf("%d", &T);
id['R'] = 0;
id['D'] = 1;
while (T--)
{
AC::init();
scanf("%d%d", &m, &n);
scanf("%s", str);
AC::ins(str, strlen(str), 0);
scanf("%s", str);
AC::ins(str, strlen(str), 1);
AC::build();
CLR(dp, 0);
dp[0][0][0][0] = 1;
for (i = 0; i <= m; ++i)
{
for (j = 0; j <= n; ++j)
{
for (u = 0; u < sz; ++u)
{
for (s = 0; s < 4; ++s)
{
if (!dp[u][i][j][s])
continue;
for (l = 0; l < 2; ++l)
{
int v = L[u].nxt[l];
dp[v][i + !l][j + l][s | L[v].cnt] = (dp[v][i + !l][j + l][s | L[v].cnt] + dp[u][i][j][s]) % mod;
}
}
}
}
}
int ans = 0;
for (i = 0; i < sz; ++i)
ans = (ans + dp[i][m][n][3]) % mod;
printf("%d\n", ans);
}
return 0;
}