题目描述
近日，谷歌研发的围棋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可以包含模板；
题解：
①反过来求不包含的方案数；
②aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZwAAADWCAYAAADl9TSHAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAAZ5SURBVHhe7d3BahtXGIbhma5KIQ7IkEWwdzak0LVzAe0NlFxnyBX0AuJtCy3YO5ssAhYkgXapajJn0kSYqeRI35xIzwOD5sSO+T2W9XrkQW4XSw1MZH563sxursoK2GfflVsA2CnBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAItrFUtmHuPnpeTO7uSqrgMvHZQdWXLwrO+yK4DCpSYLjgYVV7hcRnlIDIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAiDua11Nq2LXvT6w65eXp3J2fN8e11WfV2Oc/i9VHTPn9fVuvx9Rq3D/M85H6xrm4eegcVnBo+1WEO8/RWX7xz5/Ns+CKNUx+fVTXP0/3wMLXuh5eHzDN7+baZv3hSVtszzEPPU2oARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQ0S6Wyv5ea9u27E2vO+Tm6d2dnDXHt9dl1dvlPIvXR037/H1ZrcfXa9w+zPOQ+8W6unnoHUxwqNP89LyZ3VyVVcDl46a5eFcWULhfRDjDmUB3yM3Tc4azOfOMe8g8znAyDio4NXyqwxzm6a2e4Xw+TxejbZu9fNvMXzwpq//XxXCX82yq5nmmuP+s+vz+s9E8OzrDqeW41MJFAwBECA4AEYIDQITgAF+tlt9T+H1J3QQHgAjBASBCcIA9Mm+aV5dln9oIDrA/3iyDQ7UEB9i+D2/6M41uW+5u3WX52L+tfPCnZ03zy0lZUBvBAfbLo6dlh9oIDrB93YP+rxf9tovH/4vysX8Wl2+J4AAQITjA9k31OxyqJjgARAgOABGCA0CE4AAQITgARAgOABGCA0zjrz92e+k01REcYL90IaNKggNs3zovbfOsvOHoZMOXv/mnaT6U3Uffl52ii82ff5cFtREcYBrDnxL4cY3avLn+7+m3V783zfvuH39Y/t/Zxzd/8uynPnJUSXCAaXR/SmDdF/cc3veLbRmXR+XtfBMEB4AIwQG+Wtu2ZW9atczB/QQHgAjBASCiXSyV/b3WnWrX8KkOc5inNz89b2Y3V2W1+6dEFq+Pmvb5x0uc4JNd3i9q+D6vhTMcqjN8g3a32942/bjD+w+3U2/DHMPt1Nswx3A79TbMMdyuu236/utufElwAIg4mODU8tPGMId57meeceYZV+s89JzhABAhOABEHNRVarXoDrl5encnZ83x7XVZ9XY5z0OuRvL1GrcP87hKLcNl0WHDHObp3XdZ9E7nuXzcNBfvyuL/TX18Vpln3IPn2fB+sa5ajkstPKUGQIQznLAH/wS2I1PPM8kZDtzHGc7OCU7Yzh9QNzT1PPHgbMg848wzrpY5auEpNQAiBAeACMEBIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAiBAeACMEBIEJwAIgQHAAi2sVS2d9rbduWvel1h9w8vbuTs+b49rqseo7POPOMq3EeegcTHOo0Pz1vZjdXZQXsM2c4E+gOuXl6znA2Z55xNc5D76CCU8OnOsxhnt7qGY7jM84842qdh56LBgCIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASBCcACIEBwAIgQHgAjBASCiXSyV/b3Wtm3Zm153yM3Tuzs5a45vr8uq5/iMM8+4GuehdzDBoU7z0/NmdnNVVsA+85QaABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgARAgOABGCA0CE4AAQITgABDTNv/4+7F0vaYELAAAAAElFTkSuQmCC" alt="" />
轮廓线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;