NC20307. [SCOI2016]围棋
描述
输入描述
输入数据的第一行包含四个正整数n，m，c和q，分别表示棋盘的行数、列数、模板的列数和模板的数量。
随后2×q行，每连续两行描述一个模板。其中，每行包含c个字符，字符一定是‘W’，‘B’或‘X’中的一个，表示白子、黑子或无子三种情况的一种。
N ≤ 100,M ≤ 12,C ≤ 6,Q ≤ 5
输出描述
输出应包含q行，每行一个整数，表示符合要求的棋盘数量。
由于答案可能很大，你只需要输出答案对1,000,000,007取模后的结果即可。
示例1
输入:
3 1 1 2 B W B B
输出:
6 5
C++(g++ 7.5.0) 解法, 执行用时: 128ms, 内存消耗: 652K, 提交时间: 2023-01-07 17:08:11
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;
rg char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x){
return x=read<T>();
}
typedef long long ll;
co int mod=1e9+7;
int n,m,c,T,nxt[7],ta[6][3],tb[6][3],na,nb;
char a[8],b[8];
int id(char x) {return x=='B'?0:(x=='W'?1:2);}
int U,f[1024][6][6],g[1024][6][6],ans;
void up(int&x,int y) {x+=y;if(x>=mod)x-=mod;}
void clear() {for(int S=0;S<U;++S)for(int x=0;x<c;++x)for(int y=0;y<c;++y)g[S][x][y]=0;}
void copy() {for(int S=0;S<U;++S)for(int x=0;x<c;++x)for(int y=0;y<c;++y)f[S][x][y]=g[S][x][y];}
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
read(n),read(m),read(c),read(T);
while(T--){
scanf("%s%s",a+1,b+1);
for(int i=1;i<=c;++i)a[i]=id(a[i]),b[i]=id(b[i]);
for(int j=nxt[1]=0,i=2;i<=c;nxt[i++]=j){
while(j&&a[j+1]!=a[i]) j=nxt[j];
if(a[j+1]==a[i]) ++j;
}
na=nxt[c];
for(int i=0;i<c;++i)for(int j=0,k;j<3;++j){
for(k=i;k&&a[k+1]!=j;k=nxt[k]);
if(a[k+1]==j) ++k;
ta[i][j]=k;
}
for(int j=nxt[1]=0,i=2;i<=c;nxt[i++]=j){
while(j&&b[j+1]!=b[i]) j=nxt[j];
if(b[j+1]==b[i]) ++j;
}
nb=nxt[c];
for(int i=0;i<c;++i)for(int j=0,k;j<3;++j){
for(k=i;k&&b[k+1]!=j;k=nxt[k]);
if(b[k+1]==j) ++k;
tb[i][j]=k;
}
U=1<<(m-c+1);
for(int S=0;S<U;++S)for(int x=0;x<c;++x)for(int y=0;y<c;++y)f[S][x][y]=0;
for(int i=f[0][0][0]=1;i<=n;++i){
clear();
for(int S=0;S<U;++S)for(int x=0;x<c;++x)for(int y=0;y<c;++y)
if(f[S][x][y]) up(g[S][0][0],f[S][x][y]);
copy();
for(int j=1;j<=m;++j){
clear();
for(int S=0;S<U;++S)for(int x=0;x<c;++x)for(int y=0;y<c;++y)
if(f[S][x][y]) for(int k=0,A,B,E;k<3;++k){
E=S;
if(j>=c) if(S>>(j-c)&1) E^=1<<(j-c); // init
A=ta[x][k];
if(A==c) E|=1<<(j-c),A=na;
B=tb[y][k];
if(B==c){
if(S>>(j-c)&1) continue;
B=nb;
}
up(g[E][A][B],f[S][x][y]);
}
copy();
}
}
ans=1;
for(int i=n*m;i;--i) ans=3LL*ans%mod;
for(int S=0;S<U;++S)for(int x=0;x<c;++x)for(int y=0;y<c;++y) up(ans,mod-f[S][x][y]);
printf("%d\n",ans);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 380ms, 内存消耗: 2128K, 提交时间: 2020-05-31 16:03:08
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1000000007;
const int maxn=7;
const int maxv=1<<12;
int n,m,c,Q,maxx,a1[maxn],a2[maxn],nxt1[maxn],nxt2[maxn],t1[maxn][3],t2[maxn][3],f[2][maxv][maxn][maxn],cur,ans;
char s1[maxn],s2[maxn];
inline int getid(char x)
{
if(x=='W')return 0;
if(x=='B')return 1;
if(x=='X')return 2;
}
int powmod(int a,int k)
{
ll ret=1,x=a;
while(k)
{
if(k&1)ret=ret*x%mod;
x=x*x%mod;
k>>=1;
}
return (int)ret;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&c,&Q);
maxx=1<<(m-c+1);
while(Q--)
{
scanf("%s%s",s1+1,s2+1);
for(int i=1;i<=c;i++)a1[i]=getid(s1[i]),a2[i]=getid(s2[i]);
for(int i=2,j=0;i<=c;i++)
{
while(j&&a1[j+1]!=a1[i])j=nxt1[j];
if(a1[j+1]==a1[i])j++;
nxt1[i]=j;
}
for(int i=2,j=0;i<=c;i++)
{
while(j&&a2[j+1]!=a2[i])j=nxt2[j];
if(a2[j+1]==a2[i])j++;
nxt2[i]=j;
}
for(int i=0;i<c;i++)for(int j=0,k=i;j<3;j++,k=i)
{
while(k&&a1[k+1]!=j)k=nxt1[k];
if(a1[k+1]==j)k++;
t1[i][j]=k;
}
for(int i=0;i<c;i++)for(int j=0,k=i;j<3;j++,k=i)
{
while(k&&a2[k+1]!=j)k=nxt2[k];
if(a2[k+1]==j)k++;
t2[i][j]=k;
}
memset(f[0],0,sizeof f[0]);
f[0][0][0][0]=1;cur=1;
for(int i=1;i<=n;i++)
{
memset(f[cur],0,sizeof f[cur]);
for(int j=0;j<maxx;j++)for(int a=0;a<c;a++)
for(int b=0;b<c;b++)f[cur][j][0][0]+=f[1-cur][j][a][b],f[cur][j][0][0]%=mod;
cur=1-cur;
for(int j=1;j<=m;j++)
{
memset(f[cur],0,sizeof f[cur]);
for(int k=0;k<maxx;k++)for(int a=0;a<c;a++)
for(int b=0;b<c;b++)if(f[1-cur][k][a][b])
for(int col=0;col<3;col++)
{
int pa=t1[a][col],pb=t2[b][col],S=k;
if(j>=c)if((S>>j-c)&1)S^=1<<j-c;
if(pa==c){S^=1<<j-c;pa=nxt1[c];}
if(pb==c){if((k>>j-c)&1)continue;pb=nxt2[c];}
f[cur][S][pa][pb]+=f[1-cur][k][a][b];
f[cur][S][pa][pb]%=mod;
}
cur=1-cur;
}
}
ans=powmod(3,n*m);
for(int i=0;i<maxx;i++)for(int j=0;j<c;j++)for(int k=0;k<c;k++)
ans=(ans-f[1-cur][i][j][k]%mod+mod)%mod;
printf("%d\n",ans);
}
return 0;
}