CF578F Mirror Box 题解

CF578F Mirror Box

题意

• 在一个 $n \times m$ 的网格中，每个格子里都有一个呈 \ 或 / 状的镜子。
• 一个合法的网格需要满足从任意一个边界段垂直射进网格中，光线会从相邻的边界段射出，同时网格中的每一段都被至少一条光线穿透。
• 现在网格中有 $k$ 个位置的镜子形状不确定，求有多少种合法的网格。
• $n,m \le 100$，$k \le 200$，答案对质数 $p$ 取模。

题解

对 $(n + 1)(m + 1)$ 个顶点进行黑白相间染色。

如果把一面镜子看成一条边的话，那么一面镜子连接了两个颜色相同的顶点。

有结论：合法的网格的充要条件是某种颜色的点形成了一棵树。证明略。

枚举黑/白点形成了树，把已知的边缩起来，对不确定的位置连两条边，然后直接使用矩阵树定理求解即可，时间复杂度 $\mathcal O(k^3)$。

代码

const int N = 107, K = 207;
int n, m, f[N*N], fa[N*N], p[N*N], q[N*N];
char s[N][N];
bool ok[2] = {1, 1};
modint a[K][K];

inline int g(int x, int y) {
	return x * (m + 1) + y;
}

inline void G(int &x, int &y, int z) {
	x = z / (m + 1), y = z % (m + 1);
}

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

inline void add(int x, int y) {
	a[x][x] += 1, a[y][y] += 1, a[x][y] -= 1, a[y][x] -= 1;
}

inline modint calc(int o) {
	if (!ok[o]) return 0;
	for (int i = 0; i < (n + 1) * (m + 1); i++) fa[i] = f[i];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == '*') {
				int a = i, b = j, c = i - 1, d = j - 1;
				if (((i ^ j) & 1) != o) swap(a, c);
				int x = get(g(a, b)), y = get(g(c, d));
				if (x != y) f[x] = y;
			}
	int rt = get(o);
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			if (((i ^ j) & 1) == o && get(g(i, j)) != rt) return 0;
	for (int i = 0; i < (n + 1) * (m + 1); i++) f[i] = fa[i];
	int t = 0;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			if (((i ^ j) & 1) == o) {
				int x = g(i, j);
				if (x == get(x)) p[++t] = x, q[x] = t;
			}
	for (int i = 1; i <= t; i++)
		for (int j = 1; j <= t; j++)
			a[i][j] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == '*') {
				int a = i, b = j, c = i - 1, d = j - 1;
				if (((i ^ j) & 1) != o) swap(a, c);
				int x = get(g(a, b)), y = get(g(c, d));
				if (x != y) add(q[x], q[y]);
			}
	modint ans = 1;
	for (int i = 1; i < t; i++) {
		for (int j = i + 1; j < t; j++)
			while (a[j][i] != 0) {
				int d = a[i][i].x / a[j][i].x;
				for (int k = i; k < t; k++)
					a[i][k] -= d * a[j][k];
				swap(a[i], a[j]), ans = -ans; 
			}
		ans *= a[i][i];
	}
	return ans;
}

int main() {
	rd(n), rd(m), rd(P);
	for (int i = 0; i < (n + 1) * (m + 1); i++) f[i] = i;
	for (int i = 1; i <= n; i++) {
		rds(s[i], m);
		for (int j = 1; j <= m; j++)
			if (s[i][j] != '*') {
				int a = i, b = j, c = i - 1, d = j - 1;
				if (s[i][j] == '/') swap(a, c);
				int x = get(g(a, b)), y = get(g(c, d));
				if (x == y) ok[(a^b)&1] = 0;
				else f[x] = y;
			}
	}
	print(calc(0) + calc(1));
	return 0;
}