这道题挺有意思的,导致我甚至一度看不懂题意

看了网上仅有的两篇题解(而我都看得不太懂

都发现了文上歪歪扭扭的“轮廓线DP“字样,看了许久,才从字里行缝中看见惊人的二字”不会“

于是恶补了一下轮廓线DP,正常的状态压缩是行行之间,或者是列列之间进行状态的枚举、转移。

而轮廓线DP,可以说是格子到格子,也就是轮廓的改变,放张图自己感受一下。

无标题.jpg

比如之前状态就是$s$,所有的红色格子,现在从$(i,j-1)$到了$(i,j)$,也就是状态$t$,把$(i-1,j)$的红色格子替换成了$(i,j)$的绿色格子。

轮廓线DP的大致意思就是这样。

回归正题

题意描述:对于每一询问,给你一个两行的模式串,问有多少种方法可以把这两个模式串塞入($n,m$)大小的地图。

如果正向求的话,需要枚举塞一个,还是很多个,相当不好处理。

不妨用总方案$3^{nm}$减去不合法方案数。

但正常的状态压缩DP,复杂度过高,不适宜套在此处。

若当前填到$(i,j)$,自然可以想到这是第一行,还是第二行模式串。

那么会有一个状态记录当前填到$(i,j)$(匹配的最后一个字符一定是$col_{(i,j)}$),已经匹配到第一行模式串第$x$位,第二行模式串第$y$位,($tips:$这里的第一行,第二行,不是同一个模式串哦)。

若扩展到$(i,j+1)$,那么要继承最优匹配位置,可以用$kmp$求得$tx,ty$。

那怎么样判断当前方案是否合法?

这就要借助轮廓了,若当前状态$s$,记录以当前行$i$为第一行模式串,以$j$作为第一行模式串的结尾,是否完美匹配,若是则这一位为$1$,否则这一位为$0$。

还是用回上面的图,

无标题.jpg

观察发现,要由$s$到$t$,仅需改变$(i-1,j)$到$(i,j)$这一位的状态,因此$t$的大部分状态都可以继承$s$。根据这个是否可以搞出一些事情?

比如$ty==c$,并且$(i-1,j)$这一个位置(也就是$s$的$j-c$位为$1$)恰好也是匹配的,那不就成了合法方案了吗?

因此这样的状态可以弃之不要。

进入到下一行的时候,根据定义需要重置$x,y$。

之后就是常规操作啦!

总结流程

定义状态$f_{i,j,s,x,y}$表示当前填到$(i,j)$,轮廓$s$表示模式串第一行在相应位置是否匹配,$x$表示第一行模式串匹配到哪了,$y$表示第二行模式串匹配到哪了的不合法方案数。

通过枚举颜色$col_{i,j+1}$,$kmp$跳最优进行转移。

不要忘了进到下一行重置$x,y$。

这道题在轮廓线DP算简单的?

我还是太菜了。

代码是借鉴了别人的,所以雷同不要介意。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=1e9+7;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int nxt1[12],nxt2[12],d1[12],d2[12];char s1[12],s2[12];
int f[2][1<<12][7][7],n,m,c,q;
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void mul(int &x,int y){x=1ll*x*y%mod;}
void init(char *s,int *d,int *nxt)
{
    for(int i=1;i<=c;i++)d[i]=(s[i]=='W'?2:(s[i]=='B'));
    for(int j=0,i=2;i<=c;i++)
    {
        while(j&&d[j+1]!=d[i])j=nxt[j];
        if(d[j+1]==d[i])++j;nxt[i]=j;
    }
}
int get(int p,int col,int *d,int *nxt)
{
    while(p&&d[p+1]!=col)p=nxt[p];
    if(d[p+1]==col)++p;return p;
}
int main()
{
    qr(n),qr(m),qr(c),qr(q);
    while(q--)
    {
        memset(d1,-1,sizeof(d1));memset(nxt1,0,sizeof(nxt1));
        memset(d2,-1,sizeof(d2));memset(nxt2,0,sizeof(nxt2));
        scanf("%s",s1+1);init(s1,d1,nxt1);
        scanf("%s",s2+1);init(s2,d2,nxt2);
        int sum=1,ans=0,now=0,tx,ty,t,l=m-c+1;
        memset(f,0,sizeof(f));f[now][0][0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                memset(f[now^1],0,sizeof f[now^1]);
                for(int s=0;s<1<<l;s++)
                    for(int x=0;x<=c;x++)
                        for(int y=0;y<=c;y++)    
                            if(f[now][s][x][y])
                                for(int col=0;col<3;col++)
                                {
                                    int tx=get(x,col,d1,nxt1);
                                    int ty=get(y,col,d2,nxt2);
                                    if(j>=c)
                                    {
                                        t=s&(~(1<<j-c));
                                        t|=(tx==c)<<j-c;
                                    }
                                    else t=s;
                                    if(j>=c&&(s>>j-c&1)&&ty==c)continue;
                                    add(f[now^1][t][tx][ty],f[now][s][x][y]);
                                }
                now^=1;mul(sum,3);
            }
            for(int s=0;s<1<<l;s++)
                for(int x=0;x<=c;x++)
                    for(int y=0;y<=c;y++)
                        if(x||y)add(f[now][s][0][0],f[now][s][x][y]),f[now][s][x][y]=0;
        }
        for(int s=0;s<1<<l;s++)
            add(ans,f[now][s][0][0]);
        add(sum,mod-ans);
        qw(sum);puts("");
    }
    return 0;
}