【BZOJ 4572】【SCOI 2016】围棋

http://www.lydsy.com/JudgeOnline/problem.php?id=4572

轮廓线DP：设\(f(i,j,S,x,y)\)。

\(S\)表示\((i,1)\)到\((i,j)\)和\((i-1,j+1)\)到\((i-1,m)\)的长度为m的轮廓线上与每个位置作为末位是否与第一个串匹配的状态。

\(x,y\)分别表示\((i,j)\)这个位置作为末位与第一/二个串kmp到了哪个位置。

\(x,y\)取值范围是\([0,c)\)，因为当\(x,y\)其一取到c时，这个状态主要考虑对下一个位置上状态的贡献，所以会沿着失配指针往前跳一个继续匹配，不如把\(x/y=c\)的状态和\(x/y=fail[c]\)的状态压在一起。

注意有的连通性状压轮廓线长度为m+1，这个不关心8联通，所以长度为m。

又因为\(S\)的前\(c-1\)位一定是0，可以不记录这几位，所以S的长度是\(m-c+1\)。

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

注意滚动数组一定要全部清空！

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int mo = 1000000007;

int n, m, c, q, r1[10], r2[10], fail1[10], fail2[10];

int f[1 << 12][6][6], g[1 << 12][6][6], t1[10][10], t2[10][10];

char c1[10], c2[10];

int change(int S, int tmp, int mark) {

	if (tmp < 0) return S;

	return S ^ ((mark ^ ((S >> tmp) & 1)) << tmp);

}

int ipow(int a, int b) {

	int ret = 1, w = a;

	while (b) {

		if (b & 1) ret = 1ll * ret * w % mo;

		w = 1ll * w * w % mo;

		b >>= 1;

	}

	return ret;

}

int main() {

	scanf("%d%d%d%d", &n, &m, &c, &q);

	int ans_tot = ipow(3, n * m);

	while (q--) {

		scanf("%s%s", c1 + 1, c2 + 1);

		for (int i = 1; i <= c; ++i) {if (c1[i] == 'W') r1[i] = 1; if (c1[i] == 'B') r1[i] = 2; if (c1[i] == 'X') r1[i] = 0;}

		for (int i = 1; i <= c; ++i) {if (c2[i] == 'W') r2[i] = 1; if (c2[i] == 'B') r2[i] = 2; if (c2[i] == 'X') r2[i] = 0;}

		int p = 0;

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

			while (p && r1[p + 1] != r1[i]) p = fail1[p];

			fail1[i] = r1[p + 1] == r1[i] ? ++p : 0;

		}

		p = 0;

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

			while (p && r2[p + 1] != r2[i]) p = fail2[p];

			fail2[i] = r2[p + 1] == r2[i] ? ++p : 0;

		}

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

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

				p = i; while (p && r1[p + 1] != j) p = fail1[p];

				t1[i][j] = r1[p + 1] == j ? p + 1 : 0;

				p = i; while (p && r2[p + 1] != j) p = fail2[p];

				t2[i][j] = r2[p + 1] == j ? p + 1 : 0;

			}

		memset(f, 0, sizeof(f));

		memset(g, 0, sizeof(g));

		g[0][0][0] = 1;

		int bas = (1 << (m - c + 1)) - 1, newx, newy, T;

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

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

				if (j != 1) memcpy(f, g, sizeof(f));

				else {

					memset(f, 0, sizeof(f));

					for (int S = 0; S <= bas; ++S)

						for (int x = 0; x < c; ++x)

							for (int y = 0; y < c; ++y)

								if (g[S][x][y])

									(f[S][0][0] += g[S][x][y]) %= mo;

				}

				memset(g, 0, sizeof(g));

				for (int S = 0; S <= bas; ++S)

					for (int x = 0; x < c; ++x)

						for (int y = 0; y < c; ++y)

							if (f[S][x][y])

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

									newx = t1[x][now]; newy = t2[y][now];

									if (newy == c && j - c >= 0 && ((S >> (j - c)) & 1)) continue;

									if (newx == c) T = change(S, j - c, 1);

									else T = change(S, j - c, 0);

									if (newx == c) newx = fail1[c];

									if (newy == c) newy = fail2[c];

									(g[T][newx][newy] += f[S][x][y]) %= mo;

								}

			}

		}

		int ans = ans_tot;

		for (int S = 0; S <= bas; ++S)

			for (int x = 0; x < c; ++x)

				for (int y = 0; y < c; ++y)

					((ans -= g[S][x][y]) += mo) %= mo;

		printf("%d\n", ans);

	}

}

巴特西

【BZOJ 4572】【SCOI 2016】围棋

最新文章

热门文章