CodeForces 578F Mirror Box

CodeForces 578F Mirror Box

https://codeforces.com/contest/578/problem/F

Tutorial

https://codeforces.com/blog/entry/20368

观察发现,假如我们令坐标之和为奇数的点为红点,坐标之和为偶数的点为蓝点,则合法的条件就是镜子构成了一个红点或蓝点的生成树.

所以用矩阵树定理统计即可.

由于不确定的格子数小于等于 (200) ,所以缩点后图中最多有 (400) 个点,复杂度可以接受.

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define inver(a) power(a,MOD-2)
using namespace std;
typedef long long ll;
const int maxn=100+5;
const int maxm=100+5;
const int maxnode=maxn*maxm;
const int maxcnt=400+5;
int n,m,MOD;
int id[maxnode];
int C[maxcnt][maxcnt];
char a[maxn][maxm]; 
inline int add(int x) {return x>=MOD?x-MOD:x;}
inline int sub(int x) {return x<0?x+MOD:x;}
ll power(ll x,ll y) {
	ll re=1;
	while(y) {
		if(y&1) re=re*x%MOD;
		x=x*x%MOD;
		y>>=1;
	}
	return re;
}
namespace us {
	int fa[maxnode];
	void init(int n) {
		for(int i=0;i<n;++i) fa[i]=i;
	}
	int find(int a) {return a==fa[a]?a:fa[a]=find(fa[a]);}
	inline bool merge(int a,int b) {
		a=find(a),b=find(b);
		if(a==b) return 0;
		fa[a]=b; return 1;
	}
}
inline int idx(int x,int y) {return (x-1)*(m+1)+y-1;}
inline void addedge(int u,int v) {
	u=id[u],v=id[v];
	C[u][u]=add(C[u][u]+1);
	C[v][v]=add(C[v][v]+1);
	C[u][v]=sub(C[u][v]-1);
	C[v][u]=sub(C[v][u]-1);
}
int det(int n) {
//	debug("---
");
//	for(int i=1;i<=n;++i) {
//		for(int j=1;j<=n;++j) debug("%d ",C[i][j]);
//		debug("
");
//	}
	int re=1;
	for(int i=1;i<=n;++i) {
		int k=-1;
		for(int j=i;j<=n;++j) if(C[j][i]) {
			k=j; break;
		}
		if(k==-1) return 0;
		if(k!=i) {
			for(int j=i;j<=n;++j) swap(C[i][j],C[k][j]);
			re=sub(-re);
		}
		re=(ll)re*C[i][i]%MOD;
		int r=inver(C[i][i]);
		for(int j=i;j<=n;++j) C[i][j]=(ll)C[i][j]*r%MOD;
		for(int j=i+1;j<=n;++j) {
			for(int h=n;h>=i;--h) {
				C[j][h]=sub(C[j][h]-(ll)C[i][h]*C[j][i]%MOD);
			}
		}
	}
	return re;
}
int sol(int k) {
	us::init((n+1)*(m+1));
	for(int x=1;x<=n;++x) for(int y=1;y<=m;++y) {
		if(a[x][y]=='/') {
			if((~(x+y)&1)^k) continue;
			if(!us::merge(idx(x+1,y),idx(x,y+1))) return 0;
		}
		else if(a[x][y]=='\') {
			if(((x+y)&1)^k) continue;
			if(!us::merge(idx(x,y),idx(x+1,y+1))) return 0;
		}
	}
	int cnt=0;
	for(int x=1;x<=n+1;++x) for(int y=1;y<=m+1;++y) if((~(x+y)&1)^k) {
		int r=us::find(idx(x,y));
		if(!id[r]) id[r]=++cnt;
	}
	memset(C,0,sizeof(C));
	for(int x=1;x<=n;++x) for(int y=1;y<=m;++y) if(a[x][y]=='*') {
		if((~(x+y)&1)^k) {
			addedge(us::find(idx(x,y)),us::find(idx(x+1,y+1)));
		}
		else {
			addedge(us::find(idx(x+1,y)),us::find(idx(x,y+1)));
		}
	} 
	return det(cnt-1);
}
int main() {
	scanf("%d%d%d",&n,&m,&MOD);
	for(int i=1;i<=n;++i) scanf("%s",a[i]+1); 
	printf("%d
",add(sol(0)+sol(1)));
	return 0;
}