字符集大小为3. 在n*m棋盘的格子上填字符, 问有多少种方案能匹配上某2*c的模板. q组数据. (n≤100,m≤12,c≤6,q≤5) 如果只有一维, 那就是[HNOI2008]GT考试, 这也启发我们考虑问题的反面.
现在是二维的......题解没有看懂, 去学习了一下轮廓线DP, 豁然开朗.
从上往下, 从左往右确定每个格子填什么.
如图, 当前待决策的格子是(i,j). 当且仅当 (i-1,j-c+1) ~ (i-1,j) 能匹配上模板的第一行, (i,j-c+1) ~ (i,j) 能匹配上模板的第二行, 决策不合法. 对模板的两行建AC自动机. 只要用一个0-1串记录以轮廓线上每个格子 (绿色部分) 结尾是否可以匹配模板的第一行, (i,0) ~ (i,j-1) 走到AC自动机的哪个节点, 就能完成转移了.
跑起来好慢......又去看了下Claris爷的题解, 发现0-1串不用记录每行前(c-1)个格子的状态. 这样, 时间复杂度
const int SIGMA = 3, C = 6, L = 2*C + 1, N = 100, M = 12, S = (1<<M)+1, MOD = 1e9 + 7;
struct AC {
int ptr, ch[L][SIGMA], f[L];
void init()
{
ptr = 0;
fill_n(*ch, L*SIGMA, 0);
fill_n(f, L, 0);
}
int insert(char* s, int l)
{
int x = 0;
rep (i, 0, l) {
int c = s[i];
if (!ch[x][c]) ch[x][c] = ++ptr;
x = ch[x][c];
}
return x;
}
void build()
{
queue<int> Q;
rep (i, 0, SIGMA) {
int v = ch[0][i];
if (v) Q.push(v);
}
while (!Q.empty()) {
int u = Q.front();
Q.pop();
rep (i, 0, SIGMA) {
int& v = ch[u][i], w = ch[f[u]][i];
if (v) {
f[v] = w;
Q.push(v);
} else {
v = w;
}
}
}
}
} ac;
int l, n, m, r[2], dp[N+1][M][L][S];
int solve()
{
rep (i, 0, n+1) rep (j, 0, m) rep (k, 0, ac.ptr+1) rep (s, 0, 1<<(m-l+1)) dp[i][j][k][s] = 0;
dp[0][0][0][0] = 1;
rep (i, 0, n) rep (j, 0, m) {
int (*nxt)[S] = j == m-1 ? dp[i+1][0] : dp[i][j+1];
rep (k, 0, ac.ptr+1) rep (t, 0, 1<<(m-l+1)) {
int s = t<<(l-1), now = dp[i][j][k][t];
rep (c, 0, SIGMA) {
int x = ac.ch[k][c];
if (s & (1<<j) && x == r[1]) continue;
(nxt[j == m-1 ? 0 : x][(s & ~(1<<j) | (x == r[0]) << j) >> (l-1)] += now) %= MOD;
}
}
}
long long ans = 1;
rep (i, 0, n*m) (ans *= 3) %= MOD;
rep (s, 0, 1<<(m-l+1)) (ans -= dp[n][0][0][s]) %= MOD;
return (ans + MOD) % MOD;
}
int main()
{
int q;
char s[C+1];
scanf("%d%d%d%d", &n, &m, &l, &q);
while (q--) {
if (l > m) {
puts("0");
continue;
}
ac.init();
rep (i, 0, 2) {
scanf("%s", s);
rep (j, 0, l) s[j] = s[j] == 'X' ? 0 : (s[j] == 'W' ? 1 : 2);
r[i] = ac.insert(s, l);
}
ac.build();
printf("%d\n", solve());
}
return 0;
}