CF578F. Mirror Box

题目大意

题解

之前在看PE的Eulerian Circle那题的时候就想过生成树建图+矩阵树计数的问题，并且还想了一些做法，然后全部木大

---

结论：将图黑白染色，答案就是黑/白的生成树个数之和

第二个条件等价于图中无环，生成树即可满足

第一个条件根据左上第一个格子的情况讨论，发现两种情况刚好对应黑/白的情况，其中一个生成树中的一个块就是一对射线的路径，因为连通块个数最小所以一定相邻（自行画图）

然后中间的可以唯一确定，因此加起来就是答案

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%mod
#define ll long long
//#define file
using namespace std;

int num[101][101],fa[20001],b[201][2],bz[20001],f[202],n,m,i,j,k,l,mod,Mod,tot,N;
ll a[202][202],ans;
char ch;

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
int gf(int t) {if (fa[t]==t) return t;fa[t]=gf(fa[t]);return fa[t];}
void link(int x,int y) {if (gf(x)!=gf(y)) fa[fa[x]]=fa[y]; else {printf("0
");exit(0);}}

void work(int s)
{
	int i,j,k,l;
	ll ans=1;
	
	memset(bz,0,sizeof(bz));
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	N=0;
	fo(i,0,n)
	{
		fo(j,0,m)
		if (((i+j)&1)==s && gf(num[i][j])==num[i][j])
		bz[num[i][j]]=++N;
	}
	
	if (N>tot+1) return;
	fo(i,1,tot)
	{
		if (((b[i][0]+b[i][1])&1)==s) k=num[b[i][0]-1][b[i][1]-1],l=num[b[i][0]][b[i][1]];
		else k=num[b[i][0]-1][b[i][1]],l=num[b[i][0]][b[i][1]-1];
		k=bz[gf(k)],l=bz[gf(l)];
		if (k!=l) ++a[k][l],++a[l][k];
	}
	
	fo(i,1,N)
	{
		fo(j,1,N)
		if (i!=j)
		add(a[i][i],a[i][j]),a[i][j]=-a[i][j];
	}
	
	fo(i,1,N-1)
	{
		fo(j,1,N-1)
		if (a[i][j])
		{
			if (!f[j])
			{
				f[j]=i,ans=ans*a[i][j]%mod,a[i][j]=qpower(a[i][j],Mod);
				fo(k,j+1,N-1) a[i][k]=a[i][k]*a[i][j]%mod;
				a[i][j]=1;
				break;
			}
			else
			{
				fo(k,j+1,N-1) add(a[i][k],-a[i][j]*a[f[j]][k]);
				a[i][j]=0;
			}
		}
	}
	
	fo(i,1,N-1) if (!f[i]) ans=0;
	fo(i,1,N-2)
	{
		fo(j,i+1,N-1)
		if (f[i]>f[j])
		ans=-ans;
	}
	add(::ans,ans);
}

int main()
{
	#ifdef file
	freopen("CF578F.in","r",stdin);
	#endif
	
	scanf("%d%d%d",&n,&m,&mod),Mod=mod-2;
	fo(i,0,n) fo(j,0,m) num[i][j]=i*(m+1)+j+1,fa[num[i][j]]=num[i][j];
	fo(i,1,n)
	{
		fo(j,1,m)
		{
			ch=getchar();
			while (ch!='/' && ch!='\' && ch!='*') ch=getchar();
			if (ch=='/')  link(num[i-1][j],num[i][j-1]);
			if (ch=='\') link(num[i-1][j-1],num[i][j]);
			if (ch=='*') ++tot,b[tot][0]=i,b[tot][1]=j;
		}
	}
	
	work(0),work(1);
	printf("%lld
",(ans+mod)%mod);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}