[BZOJ4572][Scoi2016]围棋
试题描述
近日，谷歌研发的围棋AI—AlphaGo以4:1的比分战胜了曾经的世界冠军李世石，这是人工智能领域的又一里程碑。与传统的搜索式AI不同，AlphaGo使用了最近十分流行的卷积神经网络模型。在卷积神经网络模型中，棋盘上每一块特定大小的区域都被当做一个窗口。例如棋盘的大小为5×6，窗口大小为2×4，那么棋盘中共有12个窗口。此外，模型中预先设定了一些模板，模板的大小与窗口的大小是一样的。下图展现了一个5×6的棋盘和两个2×4的模板。对于一个模板，只要棋盘中有某个窗口与其完全匹配，我们称这个模板是被激活的，否则称这个模板没有被激活。例如图中第一个模板就是被激活的，而第二个模板就是没有被激活的。我们要研究的问题是：对于给定的模板，有多少个棋盘可以激活它。为了简化问题，我们抛开所有围棋的基本规则，只考虑一个n×m的棋盘，每个位置只能是黑子、白子或无子三种情况，换句话说，这样的棋盘共有3n×m种。此外，我们会给出q个2×c的模板。我们希望知道，对于每个模板，有多少种棋盘可以激活它。强调：模板一定是两行的。
输入
输入数据的第一行包含四个正整数n，m，c和q，分别表示棋盘的行数、列数、模板的列数和模板的数量。随后2×q行，每连续两行描述一个模板。其中，每行包含c个字符，字符一定是‘W’，‘B’或‘X’中的一个，表示白子、黑子或无子三种情况的一种。N<=100,M<=12,C<=6,Q<=5
输出
输出应包含q行，每行一个整数，表示符合要求的棋盘数量。由于答案可能很大，你只需要输出答案对1,000,000,007取模后的结果即可。
输入示例
3 1 1 2 B W B B
输出示例
6 5
数据规模及约定
见“输入”
题解
看到模板只有两行，就可以考虑用轮廓线 dp 做了。轮廓线的状态就一定分两行，对于上一行我们只需要关心是否完全匹配了模板的第一行就好了。
于是设计出状态 f(i, j, S, p1, p2) 表示现在在表格第 i 行第 j 列的位置，轮廓线状态为 S（如果某一位上二进制是 1 则表示这一位往前数 C 位得到的串与模板第一行完全相同），p1 和 p2 分别表示当前行已经填的串和模板的第一行、第二行的 KMP 上的匹配位置。转移显然。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 110
#define maxm 15
#define maxc 10
#define maxs 4096
#define MOD 1000000007
#define LL long long
int n, m, C, f[2][maxm][maxs][maxc][maxc];
struct KMP {
int S[maxc], f[maxc], to[maxc][3];
void init() {
memset(f, 0, sizeof(f));
return ;
}
void getstr() {
char c = getchar();
while(!isalpha(c)) c = getchar();
for(int i = 1; i <= C; i++, c = getchar())
if(c == 'X') S[i] = 0;
else if(c == 'B') S[i] = 1;
else S[i] = 2;
for(int i = C + 1; i < maxc; i++) S[i] = 233;
return ;
}
void getfail() {
f[1] = f[2] = 1;
for(int i = 2; i <= C; i++) {
int j = f[i];
while(j > 1 && S[j] != S[i]) j = f[j];
f[i+1] = S[j] == S[i] ? j + 1 : 1;
}
for(int i = 1; i <= C + 1; i++)
for(int c = 0; c < 3; c++) {
int j = i;
while(j > 1 && S[j] != c) j = f[j];
to[i][c] = S[j] == c ? j + 1 : 1;
}
return ;
}
} l1, l2;
void up(int& a, int b) {
a += b; if(a >= MOD) a -= MOD;
return ;
}
int main() {
n = read(); m = read(); C = read(); int q = read();
while(q--) {
l1.init(); l1.getstr(); l1.getfail();
l2.init(); l2.getstr(); l2.getfail();
memset(f, 0, sizeof(f));
int all = (1 << m) - 1; bool cur = 0;
f[cur][1][0][1][1] = 1;
for(int i = 1; i <= n; i++, cur ^= 1) {
memset(f[cur^1], 0, sizeof(f[cur^1]));
int tmp = 0;
for(int S = 0; S <= all; S++) up(tmp, f[cur][1][S][1][1]);
for(int j = 1; j <= m; j++)
for(int S = 0; S <= all; S++)
for(int p1 = 1; p1 <= C + 1; p1++)
for(int p2 = 1; p2 <= C + 1; p2++) {
int& ans = f[cur][j][S][p1][p2];
if(!ans) continue;
for(int c = 0; c < 3; c++) {
int t1 = l1.to[p1][c], t2 = l2.to[p2][c];
if((S & 1) && t2 == C + 1) continue;
int tS = S >> 1 | ((t1 == C + 1) << m - 1);
if(j < m) up(f[cur][j+1][tS][t1][t2], ans);
else up(f[cur^1][1][tS][1][1], ans);
}
}
}
int ans = 0; LL sum = 1;
for(int S = 0; S <= all; S++) up(ans, f[cur][1][S][1][1]);
for(int i = 1; i <= n * m; i++) (sum *= 3) %= MOD;
printf("%d
", (int)((sum - ans + MOD) % MOD));
}
return 0;
}