题意

题目链接

做法

首先你得先轮廓线DP（不一定得会插头DP，但这两玩意好像没差）

题解部分照搬：https://www.luogu.com.cn/blog/duyi/solution-p3290，讲的挺好的。

先做补集转化。把“至少有一次匹配”，转化为求“禁止出现匹配”。然后用$3^{nm}$减去禁止出现匹配的方案数，就是答案了。

考虑轮廓线DP。

设 $dp[i][j][mask][k][l]$ 表示考虑到了第 $i$ 行、第 $j$ 列这个位置。$mask$ 是一个状压，表示当前轮廓线哪些位置可以与模板的第一行完全匹配。由于 $1…c−1$ 这些列显然不可能完全匹配，所以 $mask$ 只需要记录 $m-c+1$ 个二进制位。$k$ 表示第 $i$ 行 $1…j$ 位最多能匹配到模板串第一行的哪个位置，$l$ 表示第 $i$ 行 $1…j$ 位最多能匹配到模板串第二行的哪个位置。

显然，当 $l=c$ 且 $mask$ 的第一个二进制位（也就是代表了 $i,j$ 正上方的位置）为 $1$ 时，就会出现一次和模板串的完整匹配，因此这种转移是不合法的。否则，其他情况下我们都可以转移。新的 $k,l$ 可以用 $KMP$ 求出。新的 $mask$ 相比原来的 $mask$ 要去掉第一位，然后新加入一位：若 $k=c$ 则新加入的位为 $1$，否则为 $0$ 。

DP 数组的前两维可以滚动使用，这样优化了空间。

注意，在 DP 完一整行后，要把所有方案数，累加到 $dp[i][j][mask][0][0]$ 上：因为下一行又要重新开始匹配了。

时间复杂度：$O(nm2^{m-c+1}c^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<cstring>
using  namespace  std;
typedef  long  long  LL;
const  LL  mod=1000000007;
inline  LL  ksm(LL  x,int  y)
{
	LL  ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}
	return  ans;
}
LL  dp[2][4100][10][10];//滚动数组
int  kmp[2][10],a[2][10];
char  st[2][10];
int  n,m,q,c;
inline  int  get(int  k,int  x){return  (k&(1<<(x-c)))>0;}
inline  void  change(int  &k,int  x,int  val)
{
	if(k&(1<<(x-1)))k^=(1<<(x-1));
	k|=(val<<(x-1));
}
int  main()
{
	scanf("%d%d%d%d",&n,&m,&c,&q);
	int  limit=(1<<(m-c+1))-1;
	for(int  t=1;t<=q;t++)
	{
		for(int  i=0;i<=1;i++)
		{
			scanf("%s",st[i]+1);
			kmp[i][0]=-1;a[i][0]=a[i][c+1]=-1;
			int  k=-1;
			for(int  j=1;j<=c;j++)
			{
				a[i][j]=(st[i][j]=='W'?1:(st[i][j]=='B'?2:0));
				while(k!=-1  &&  st[i][k+1]!=st[i][j])k=kmp[i][k];
				kmp[i][j]=++k;
			}
		}
		int  now=0,pre=1;
		memset(dp[now],0,sizeof(dp[now]));
		dp[now][0][0][0]=1;//初始化为1 
		for(int  i=1;i<=n;i++)
		{
			for(int  j=1;j<=m;j++)
			{
				now^=1;pre^=1;
				memset(dp[now],0,sizeof(dp[now]));
				for(int  k=0;k<=limit;k++)//之前的状态 
				{
					for(int  q=0;q<=c  &&  q<j;q++)//第零行 
					{
						for(int  p=0;p<=c  &&  p<j;p++)//第一行 
						{
							if(!dp[pre][k][q][p])continue;
							for(int  o=0;o<=2;o++)
							{
								int  qq=q,pp=p;
								while(qq!=-1  &&  a[0][qq+1]!=o)qq=kmp[0][qq];
								while(pp!=-1  &&  a[1][pp+1]!=o)pp=kmp[1][pp];
								qq++;pp++;
								if(pp==c  &&  get(k,j)==1)continue;
								int  kk=k;
								if(j>=c)change(kk,j-c+1,qq==c);
								dp[now][kk][qq][pp]=(dp[now][kk][qq][pp]+dp[pre][k][q][p])%mod;
							}
						}
					}
				}
			}
			now^=1;pre^=1;
			memset(dp[now],0,sizeof(dp[now]));
			for(int  k=0;k<=limit;k++)//之前的状态 
			{
				for(int  q=0;q<=c;q++)//第零行 
				{
					for(int  p=0;p<=c;p++)dp[now][k][0][0]=(dp[now][k][0][0]+dp[pre][k][q][p])%mod;
				}
			}
		}
		LL  ans=0;
		for(int  k=0;k<=limit;k++)ans=(ans+dp[now][k][0][0])%mod;
		printf("%lld\n",(ksm(3,n*m)-ans+mod)%mod);
	}
	return  0;
}

小结

这道题目好难，完全不会QAQ

但是感悟也不是没有，其实轮廓线 DP 有的时候可以优化方格图上某些状压，当状压难以转移，或者可以转移但时间较大时不妨考虑轮廓线 DP 。