圍棋一二三四線圖解，2019.03.25 bzoj4572: [Scoi2016]圍棋（輪廓線dp）

傳送門
題解可以參見$zjj$神仙的，寫的很清楚。
代碼：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
const int mod=1e9+7;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=add(a,b);}
inline void modify(int&a,const int&b){a=dec(a,b);}
int ans,f[2][1<<12|5][13][13],n,m,c,q,a[13],fail[2][13],trans[2][13][3],tmp;
char s[13];
inline int idx(const char&x){return x=='W'?0:(x=='B'?1:2);}
int main(){scanf("%d%d%d%d",&n,&m,&c,&q);while(q--){for(ri tt=0;tt<2;++tt){scanf("%s",s+1);for(ri i=1;i<=c;++i)a[i]=idx(s[i]);for(ri i=1,j=0;i<=c;++i){while(j&&s[i+1]!=s[j+1])j=fail[tt][j];s[i+1]==s[j+1]?fail[tt][i+1]=++j:fail[tt][i+1]=0;}for(ri k,i=0;i<c;++i)for(ri j=0;j<3;++j){for(k=i;k&&a[k+1]!=j;k=fail[tt][k]);trans[tt][i][j]=a[k+1]==j?k+1:0;}}memset(f[0],0,sizeof(f[0]));ans=f[0][0][0][0]=1,tmp=1;for(ri i=1;i<=n;++i){memset(f[tmp],0,sizeof(f[tmp]));for(ri j=0,up=1<<(m-c+1);j<up;++j)for(ri k=0;k<c;++k)for(ri l=0;l<c;++l)update(f[tmp][j][0][0],f[tmp^1][j][k][l]);tmp^=1;for(ri j=1;j<=m;++j,tmp^=1){ans=mul(ans,3);memset(f[tmp],0,sizeof(f[tmp]));for(ri sta=0,up=1<<(m-c+1);sta<up;++sta)for(ri k=0;k<c;++k)for(ri l=0;l<c;++l){if(!f[tmp^1][sta][k][l])continue;for(ri a,b,ns,t=0;t<3;++t){a=trans[0][k][t],b=trans[1][l][t],ns=sta;if(j>=c&&((sta>>(j-c))&1))ns^=1<<(j-c);if(a==c)ns^=1<<(j-c),a=fail[0][a];if(b==c){if((sta>>(j-c))&1)continue;b=fail[1][b];}update(f[tmp][ns][a][b],f[tmp^1][sta][k][l]);}}}}tmp^=1;for(ri i=0,up=1<<(m-c+1);i<up;++i)for(ri j=0;j<c;++j)for(ri k=0;k<c;++k)modify(ans,f[tmp][i][j][k]);cout<<ans<<'\n';}return 0;
}