围棋

状压DP好题。

容易想到 $n=2$ 的做法，用 $f_{i,j,k}$ 表示dp到第 $i$ 列，现在匹配到了 $j$ ，之前一共匹配了 $k$ 个。然后转移利用KMP就挺显然的，勉强能过。

但是想到这个部分就想不动了

首先发现 至少匹配一次 的这个条件很麻烦，考虑反着来：用总方案数-一次都不匹配的方案数。

数据这么小，考虑轮廓线状压DP，但是要状压什么呢，这是一个难点。

考虑当前位置所在行作为第二行，那么你就要判断当前行能否匹配完模板串，那么你就需要记录dp到这个位置匹配第二行匹配到了哪里。

那你怎么知道上一行匹配到了哪里呢？这里就可以考虑轮廓线那个东西了，状态 $S$ 如果当前位为1，表示上一行可以匹配完模板串的第一行，0则表示不能。

拿考虑当前位怎么更新这个状态 $S$ ，和上面那个匹配第二行的要求很形似对吧，那么我们就可以和上面匹配第二行一样的做法存一个匹配到了哪里。

至此，我们已经可以转移了，状态 $dp_{flag,S,i,j}$ 表示状压的状态为 $S$ ，当前位置匹配第一行匹配到了 $i$ ，第二行匹配到了 $j$ 。$flag$ 那一维就是滚动数组。

然后转移的时候注意一下dp到每一行最后一个位置的时候要把 $i,j$ 直接搞为0，因为下一个地方就是下一行，也就没法继承上面匹配的情况了。

上代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=20,S=(1<<12)+10,mod=1e9+7;
const char alp[5]="WBX";
int n,m,c,Q;
char s[2][N];
int dp[2][S][N][N],q[2][S*N*N][3];
int nxt[2][N];
void pre(){
	for(int t = 0; t < 2; t++){
		int j = 0;
		for(int i = 1; i < c; i++){
			while(j != 0 && s[t][i + 1] != s[t][j + 1]) j = nxt[t][j];
			if(s[t][i + 1] == s[t][j + 1]) j++;
			nxt[t][i + 1] = j;
		}
	}
}
int pos[2][N][3];
int query(int op,int x,int y){
	if (pos[op][x][y]!=-1) return pos[op][x][y];
	int now=x;
	while (now && s[op][now+1]!=alp[y]) now=nxt[op][now];
	if (s[op][now+1]==alp[y]) now++;
	return pos[op][x][y]=now;
}
int qpow(int a,int b){
	int res=1;
	for (;b;b>>=1){
		if (b&1) res=res*a%mod;
		a=a*a%mod;
	}
	return res;
}
void clear(){
	memset(nxt,0,sizeof(nxt));
	memset(dp,-1,sizeof(dp));
	memset(pos,-1,sizeof(pos));
	memset(q,0,sizeof(q));
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&c,&Q);
	while (Q--){ 
		scanf("%s",s[0]+1);
		scanf("%s",s[1]+1);
		clear();
		pre();
		int last=1,now=0,flag=1;
		dp[0][0][0][0]=1;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++){
				flag^=1;
				now=0;
				int nxt=flag^1;
				for (int u=1;u<=last;u++){
					int s=q[flag][u][0],p1=q[flag][u][1],p2=q[flag][u][2];
					for (int t=0;t<3;t++){
						int nx=query(0,p1,t),ny=query(1,p2,t),ns=s&(~(1<<(j-1)));
						if (s&(1<<(j-1)) && ny==c) continue;
						if (nx==c) ns|=(1<<(j-1));
						if (j==m) nx=ny=0;
						if (dp[nxt][ns][nx][ny]==-1){
							q[nxt][++now][0]=ns;
							q[nxt][now][1]=nx;
							q[nxt][now][2]=ny;
							dp[nxt][ns][nx][ny]=dp[flag][s][p1][p2];
						}else dp[nxt][ns][nx][ny]+=dp[flag][s][p1][p2];
						dp[nxt][ns][nx][ny]%=mod;
					}
					dp[flag][s][p1][p2]=-1;
				}
				last=now;
			}
		int ans=qpow(3,n*m);
		flag^=1;
		for (int i=1;i<=last;i++){
			ans-=dp[flag][q[flag][i][0]][q[flag][i][1]][q[flag][i][2]];
			ans%=mod;
		}
		ans=(ans%mod+mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}