「CF578F」 Mirror Box

description

solution

考虑转化题目的要求

1.对于任意一条边，都存在一条从界垂直射入的光线，经过反射穿过这条边。

当图中有环时，环内的边一定不满足条件，而在不存在环时感性理解一下就能满足条件

2.从任意一条界垂直射入的光线经过反射，从相邻的一条界射出；

对于这个条件，因为光路可逆，所以我们需要将图中的边两两分组，并用镜子将他们围住
多画几张图后，你就会发现：将图中点黑白染色后，答案一定包括一个黑色点或者白色点的生成树，并且再确定这棵树后，剩下的镜子选法只有一种
于是上矩阵树定理即可

code

#include<bits/stdc++.h>

using namespace std;

const int N=310;

int n,m,p,fa[N*N];

char s[N][N];

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

inline int find(int x){return fa[x]==x?x:fa[x]=fa[fa[x]]=fa[fa[fa[x]]]=find(fa[fa[fa[x]]]);}

inline void merge(int x,int y){x=find(x);y=find(y);x!=y?fa[x]=y:0;}

int a[2][N<<2][N<<2],tot[2],bel[N*N];

inline int add(int p,int x,int y){

	++a[p][bel[x]][bel[x]];++a[p][bel[y]][bel[y]];

	--a[p][bel[x]][bel[y]];--a[p][bel[y]][bel[x]];

}

inline int inv(int a,int b=p-2){

	int ret=1;

	while(b){

		if(b&1) ret=1ll*ret*a%p;

		a=1ll*a*a%p;b>>=1;

	}

	return ret;

}

inline int matrix_tree(int pt,int x){

	int ans=1;

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

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

			if(a[pt][i][j]){

				int d=1ll*a[pt][j][j]*inv(a[pt][i][j])%p;

				for(int k=j;k<=x;++k) a[pt][j][k]=(a[pt][j][k]-1ll*d*a[pt][i][k]%p+p)%p;

				swap(a[pt][i],a[pt][j]);ans=-ans;

			}

		}

		ans=1ll*ans*a[pt][j][j]%p;

		if(ans<0) ans+=p;

	}

	return ans;

}

int main(){

	scanf("%d%d%d",&n,&m,&p);

	for(int i=1;i<=(n+1)*(m+1);++i) fa[i]=i;

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

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

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

			if(s[i][j]=='/') merge(id(i+1,j),id(i,j+1));

			else if(s[i][j]!='。') merge(id(i,j),id(i+1,j+1));

		}

	}

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

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

			if(fa[id(i,j)]==id(i,j)){

				int wh=(i+j)&1;

				bel[id(i,j)]=++tot[wh];

			}

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

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

			if(s[i][j]=='*'){

				add((i+1+j)&1,find(id(i+1,j)),find(id(i,j+1)));

				add((i+j)&1,find(id(i,j)),find(id(i+1,j+1)));

			}

		}

	}

	printf("%d\n",(matrix_tree(0,tot[0]-1)+matrix_tree(1,tot[1]-1))%p);

	return 0;

}

巴特西

「CF578F」 Mirror Box

description

solution

code

最新文章

热门文章