bzoj2669 [cqoi2012]局部极小值状压DP+容斥

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=2669

题解

可以发现一个 \(4\times 7\) 的矩阵中，有局部最小值的点最多有 \(2\times 4 = 8\) 个，所以我们可以状压一下每个局部最小值的位置有没有被选。

从小到大填入每一个格子，那么如果一个点的周围有没有被填上的局部最小值，那么这个格子不可以被填。所以预处理一下每种状态下可以自由填多少格子，然后如果状态保持不变的话，就可以这样转移。

如果状态变化，就是说填了一个局部最小值的话，那么久直接加上当前状态的答案就可以了。

但是这样会有问题：被自由填的位置，可能会出现多余的局部最小值，也就说不该是局部最小值的地方出现了局部最小值——那么就直接容斥一下就好了，直接搜索一个各种合法状态，都 DP 一下。

这个 DP 的复杂度很显然是 \(O(nm \cdot 8 \cdot 2^8)\)，但是搜索我就不太会算了。总之可以轻松的过掉。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 4 * 7 + 7;

const int M = (1 << 8) + 7;

const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

const int P = 12345678;

int n, m, pcnt, cnt, S, ans;

pii p[N];

int wy[M], dp[N][M];

char a[N][N], b[N][N], mk[5][8];

inline int smod(int x) { return x >= P ? x - P : x; }

inline void sadd(int &x, const int &y) { x += y; x >= P ? x -= P : x; }

inline int fpow(int x, int y) {

	int ans = 1;

	for (; y; y >>= 1, x = (ll)x * x % P) if (y & 1) ans = (ll)ans * x % P;

	return ans;

}

inline void ycl() {

	S = (1 << cnt) - 1;

	memset(wy, 0, sizeof(wy));

	for (int s = 0; s <= S; ++s) {

		int &ans = wy[s];

		memset(mk, 0, sizeof(mk));

		for (int i = 1; i <= cnt; ++i) if (!((s >> (i - 1)) & 1)) {

			int x = p[i].fi, y = p[i].se;

			mk[x][y] = 1;

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

				int px = x + dx[i], py = y + dy[i];

				if (px < 1 || px > n || py < 1 || py > m) continue;

				mk[px][py] = 1;

			}

		}

		for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (!mk[i][j]) ++ans;

	}

}

inline void DP() {

	memset(dp, 0, sizeof(dp));

	dp[0][0] = 1;

	for (int i = 0; i < n * m; ++i) {

		for (int s = 0; s <= S; ++s) {

			sadd(dp[i + 1][s], (ll)dp[i][s] * (wy[s] - i) % P);

			for (int j = 1; j <= cnt; ++j) if (!((s >> (j - 1)) & 1))

				sadd(dp[i + 1][s ^ (1 << (j - 1))], dp[i][s]);

		}

	}

}

inline void calc() {

	cnt = 0;

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

		for (int j = 1; j <= m; ++j) if (b[i][j]) p[++cnt] = pii(i, j);

	ycl();

	DP();

	if ((cnt - pcnt) & 1) sadd(ans, P - dp[n * m][S]);

	else sadd(ans, dp[n * m][S]);

}

inline void dfs(int x, int y) {

	if (x == n + 1) return calc();

	if (y == m) dfs(x + 1, 1); else dfs(x, y + 1);

	int flag = 1;

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

		int px = x + dx[i], py = y + dy[i];

		if (px < 1 || px > n || py < 1 || py > m) continue;

		if (b[px][py]) { flag = 0; break; }

	}

	if (a[x][y] || !flag) return;

	b[x][y] = 1;

	if (y == m) dfs(x + 1, 1); else dfs(x, y + 1);

	b[x][y] = 0;

}

inline void work() {

	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (a[i][j])

		for (int k = 1; k <= n; ++k) for (int l = 1; l <= n; ++l) if (a[k][l])

			if (abs(i - k) <= 1 && abs(j - l) <= 1 && (i != k || j != l)) return (void)puts("0");

	memcpy(b, a, sizeof(a));

	dfs(1, 1);

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

}

inline void init() {

	read(n), read(m);

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

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

		for (int j = 1; j <= m; ++j) a[i][j] = a[i][j] == 'X', pcnt += a[i][j];

	}

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj2669 [cqoi2012]局部极小值状压DP+容斥

题目传送门

题解

最新文章

热门文章

巴特西

bzoj2669 [cqoi2012]局部极小值 状压DP+容斥

题目传送门

题解

最新文章

热门文章

bzoj2669 [cqoi2012]局部极小值状压DP+容斥