[SCOI2016]围棋

Description

近日，谷歌研发的围棋AI—AlphaGo以4:1的比分战胜了曾经的世界冠军李世石，这是人工智能领域的又一里程碑。与传统的搜索式AI不同，AlphaGo使用了最近十分流行的卷积神经网络模型。在卷积神经网络模型中，棋盘上每一块特定大小的区域都被当做一个窗口。例如棋盘的大小为5×6，窗口大小为2×4，那么棋盘中共有12个窗口。此外，模型中预先设定了一些模板，模板的大小与窗口的大小是一样的。下图展现了一个5×6的棋盘和两个2×4的模板。对于一个模板，只要棋盘中有某个窗口与其完全匹配，我们称这个模板是被激活的，否则称这个模板没有被激活。例如图中第一个模板就是被激活的，而第二个模板就是没有被激活的。我们要研究的问题是：对于给定的模板，有多少个棋盘可以激活它。为了简化问题，我们抛开所有围棋的基本规则，只考虑一个n×m的棋盘，每个位置只能是黑子、白子或无子三种情况，换句话说，这样的棋盘共有3n×m种。此外，我们会给出q个2×c的模板。我们希望知道，对于每个模板，有多少种棋盘可以激活它。强调：模板一定是两行的。

Input

输入数据的第一行包含四个正整数n，m，c和q，分别表示棋盘的行数、列数、模板的列数和模板的数量。随后2×q行，每连续两行描述一个模板。其中，每行包含c个字符，字符一定是‘W’，‘B’或‘X’中的一个，表示白子、黑子或无子三种情况的一种。N<=100,M<=12,C<=6,Q<=5

Output

输出应包含q行，每行一个整数，表示符合要求的棋盘数量。由于答案可能很大，你只需要输出答案对1,000,000,007取模后的结果即可。

Sample Input

3 1 1 2

B

W

B

B

Sample Output

6

5

这题写的真是神清气爽……题解真是神仙写法

首先看范围，\(m\)辣么小肯定要状压

考虑使用补集转化，求没有任何一个子矩阵满足匹配条件的棋盘种数，然后我们暴力状压上一行状态，逐行转移，复杂度\(O(n*3^m+3^{2*m})\)，直接TLE

改一下状压状态，因为我们只需要关系是否匹配，并不需要关心黑白或者无，所以我们可以用二进制状压

考虑使用轮廓线DP解决这个问题，设\(f_{i,j,S,x,y}\)表示当前考虑到第\(i\)行第\(j\)列，\(S\)记录轮廓线上每个点能否匹配完模板的第一行(\(S\)上第\(k\)位为1表示轮廓线上第\(k\)位，将模板第一行最后一个格子放置在此后，模板第一行颜色不会与已决策棋盘区域发生混乱)，目前匹配到模板第一行的第\(x\)列，第二行的第\(y\)列

然后前两维直接滚动掉，然后我们用KMP预处理出模板两行的失配函数，匹配的时候直接暴力枚举转移即可

每当枚举到新的一行时，要将上一行的值全部转移过来，具体实现可以看代码

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline char gc(){

	static char buf[1000000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int frd(){

	int x=0,f=1;char ch=gc();

	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x<0)    putchar('-'),x=-x;

	if (x>9)	print(x/10);

	putchar(x%10+'0');

}

const int N=(1<<12)*216,Mod=1e9+7,limit=235417;

struct S1{

	int S[N+10],x[N+10],y[N+10],v[N+10];

	int stack[N+10],top;

	void insert(int s,int _x,int _y,int val){

		ui res=s*limit*limit+_x*limit+_y; res%=N;

		if (!v[res])	stack[++top]=res,S[top]=s,x[top]=_x,y[top]=_y;

		v[res]=(v[res]+val)%Mod;

	}

	void clear(){while (top)	v[stack[top--]]=0;}

}f[2];

int v[2][10],Nxt[2][10],Fail[2][10][5];

char s[2][10];

int T(char x){return x=='B'?1:x=='W'?2:3;}

int mlt(int a,int b){

	int res=1;

	for (;b;b>>=1,a=1ll*a*a%Mod)	if (b&1)	res=1ll*res*a%Mod;

	return res;

}

int main(){

	int n=read(),m=read(),c=read(),q=read();

	while (q--){

		scanf("%s",s[0]+1);

		scanf("%s",s[1]+1);

		for (int i=1;i<=c;i++)	v[0][i]=T(s[0][i]);

		for (int i=1;i<=c;i++)	v[1][i]=T(s[1][i]);

		memset(Nxt,0,sizeof(Nxt));

		Nxt[0][0]=Nxt[1][0]=-1;

		for (int k=0;k<2;k++){

			for (int i=2,j=0;i<=c;i++){

				while (~j&&v[k][i]!=v[k][j+1])	j=Nxt[k][j];

				Nxt[k][i]=++j;

			}

		}

		for (int k=0;k<2;k++){

			for (int i=0;i<=c;i++){

				for (int j=i,x=1;x<=3;x++,j=i){

					while (~j&&x!=v[k][j+1])	j=Nxt[k][j];

					Fail[k][i][x]=++j;

				}

			}

		}

		int p=0; f[p].clear();

		f[p].insert(0,0,0,1);

		for (int i=1;i<=n;i++){

			for (int l=1;l<=f[p].top;l++)	f[p].x[l]=f[p].y[l]=0;

			for (int j=1;j<=m;j++){

				f[p^=1].clear();

				for (int l=1;l<=f[p^1].top;l++){

					int S=f[p^1].S[l],x=f[p^1].x[l],y=f[p^1].y[l];

					for (int k=1;k<=3;k++){

						int a=Fail[0][x][k],b=Fail[1][y][k];

						int tmp=(b==c)<<(j-1),sta=S;

						if (S&tmp)	continue;

						if (sta>>(j-1)&1)	sta^=1<<(j-1);

						if (a==c)	sta^=1<<(j-1);

						f[p].insert(sta,a,b,f[p^1].v[f[p^1].stack[l]]);

					}

				}

			}

		}

		int Ans=mlt(3,n*m);

		for (int i=1;i<=f[p].top;i++)	Ans=(Ans-f[p].v[f[p].stack[i]])%Mod;

		printf("%d\n",(Ans+Mod)%Mod);

	}

	return 0;

}

巴特西

[SCOI2016]围棋

最新文章

热门文章