bzoj 4031: [HEOI2015]小Z的房间【矩阵树定理】

是板子题，因为mod不是质数所以需要辗转相除然而并不知道为啥

高斯消元部分还不知道原理呢……先无脑背过的

#include<iostream>

#include<cstdio>

using namespace std;

const int N=105,dx[]={-1,1,0,0},dy[]={0,0,-1,1},mod=1e9;

int n,m,id[N][N],a[N][N],tot;

char c[N][N];

bool ok(int x,int y)

{

	return x>=1&&x<=n&&y>=1&&y<=m&&c[x][y]!='*';

}

int gaosi(int n)

{

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

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

			if(a[i][j]<0)

				a[i][j]+=mod;

	long long ans=1,f=1;

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

	{

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

		{

			long long x=a[i][i],y=a[j][i];

			while(y)

			{

				long long t=x/y;

				x%=y;

				swap(x,y);

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

					a[i][k]=(a[i][k]-a[j][k]*t%mod+mod)%mod;

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

					swap(a[i][k],a[j][k]);

				f=-f;

			}

		}

		if(!a[i][i])

			return 0;

		ans=ans*a[i][i]%mod;

	}

	return f==-1?(mod-ans)%mod:ans;

}

int main()

{

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

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

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

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

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

			if(c[i][j]!='*')

				id[i][j]=++tot;

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

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

			if(c[i][j]!='*')

				for(int k=0;k<4;k++)

					if(ok(i+dx[k],j+dy[k]))

						a[id[i][j]][id[i][j]]++,a[id[i][j]][id[i+dx[k]][j+dy[k]]]--;

	printf("%d\n",gaosi(tot-1));

	return 0;

}

巴特西

bzoj 4031: [HEOI2015]小Z的房间【矩阵树定理】

最新文章

热门文章