题目描述
近日，谷歌研发的围棋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取模后的结果即可。
题意：
nm的棋盘，有一个2*c的模板，nmc都比较小，求一共有多少种nm可以包含模板；
题解：
①反过来求不包含的方案数；
轮廓线dp。。。。把模板串分成两份，用f[i][j][S][x][y]表示在ij位置，i行的ij和第一个模板匹配到了x，和第二个模板匹配到了y，S记录红色区域(只需记录m-c+1个)和第一个模板串匹配的情况。只有在S&(1<<m-c)&&y==c时不转移；
③ij可以不用存，滚动一下方便点，注意行更新时所有f[S][x][y]都要转移到f[S][0][0],初始状态为f[0][0][0] = 1,还有当x，y到了c时最后应该变成nxt[c];
③用kmp预处理nxt，再预处理出在i位置上加上j后的失配指针ta[i][j],tb[i][j];
#include<cstdio>
#include<iostream>
const int mod = 1e9+,N = ;
using namespace std;
int n,m,c,q,a[N],b[N],nxt[N],na,nb,f[(<<)][N][N],g[(<<)][N][N],ta[N][],tb[N][],U;
char gc(){
static char *p1,*p2,s[];
if(p1==p2) p2=(p1=s)+fread(s,,,stdin);
return (p1==p2)?EOF:*p1++;
}
int rd(){
int x=; char c = gc();
while(c<''||c>'') c = gc();
while(c>=''&&c<='') x=x*+c-'',c=gc();
return x;
}
char gt(){
char c; do c=gc(); while(!isalpha(c));
return (c=='W')?:(c=='B')?:;
}
void clear(){for(int S=;S<U;S++)for(int x=;x<c;x++)for(int y=;y<c;y++)g[S][x][y]=;}
void copy(){for(int S=;S<U;S++)for(int x=;x<c;x++)for(int y=;y<c;y++)f[S][x][y]=g[S][x][y];}
void up(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int main()
{ freopen("bzoj4572.in","r",stdin);
freopen("bzoj4573.out","w",stdout);
n=rd();m=rd();c=rd();q=rd();
while(q--){
for(int i=;i<=c;i++) a[i] = gt();
for(int i=;i<=c;i++) b[i] = gt();
nxt[]=;
for(int i = ,j=;i <= c;nxt[i++]=j){
while(j&&a[j+]!=a[i]) j=nxt[j];
if(a[j+]==a[i]) j++;
}
na=nxt[c];
for(int i = ;i < c;i++) for(int j = ,k;j < ;j++){
for(k=i;k&&a[k+]!=j;k=nxt[k]);
if(a[k+]==j) k++; ta[i][j] = k;
}
nxt[]=;
for(int i = ,j=;i <= c;nxt[i++]=j){
while(j&&b[j+]!=b[i]) j=nxt[j];
if(b[j+]==b[i]) j++;
}
nb=nxt[c];
for(int i = ;i < c;i++) for(int j = ,k;j < ;j++){
for(k=i;k&&b[k+]!=j;k=nxt[k]);
if(b[k+]==j) k++; tb[i][j] = k;
}
U = (<<m-c+);
for(int S=;S<U;S++)for(int x=;x<c;x++)for(int y=;y<c;y++) f[S][x][y]=;
f[][][]=;
for(int i = ;i <= n;i++){
clear();
for(int S=;S<U;S++)for(int x=;x<c;x++)for(int y=;y<c;y++)if(f[S][x][y])up(g[S][][],f[S][x][y]);
copy();
for(int j=;j<=m;j++){
clear();
for(int S=;S<U;S++)for(int x=;x<c;x++)for(int y=;y<c;y++)if(f[S][x][y])for(int k=;k<;k++){
int E = S;
if(j>=c&&E&(<<j-c)) E^=(<<j-c);
int A = ta[x][k];
if(A==c){
E|=(<<j-c);
A=na;
}
int B = tb[y][k];
if(B==c){
if(S&(<<j-c)) continue;
B = nb;
}
up(g[E][A][B],f[S][x][y]);
}
copy();
}
}
int ans = ;
for(int i=;i<=n;i++)for(int j=;j<=m;j++) ans=1ll*ans*%mod;
for(int S=;S<U;S++)for(int x=;x<c;x++)for(int y=;y<c;y++) ans=(ans-f[S][x][y]+mod)%mod;
printf("%d\n",ans);
}
return ;
}//by tkys_Austin;