[BZOJ5133][CodePlus2017年12月]白金元首与独舞

bzoj

luogu

题意

给你一个\(n*m\)的网格，每个位置上有一个箭头指向上或下或左或右。有些位置上还没有箭头，现在要求你在这些没有箭头的位置上填入箭头，使得从网格的任意一个位置开始，都可以沿着箭头走出网格。

求填入的方案数膜\(10^9+7\)

sol

给“网格外”建一个点。每个格子向它指向的格子连一条边。

这样会发现一个方案合法当且仅当连出的这\(n*m\)条边构成一棵树。

没有确定的格子可以向四个方向连边。这样直接上矩阵树可以做到\(O((nm)^3)\)。

考虑优化。只对所有未确定的格子以及“网格外”建点，这样就只有\(k+1\)个点。每个未确定的格子向四个方向能走到的第一个未确定格子或是“网格外”连边。

具体实现可以用记搜，同时记录一下每个状态是否在搜索栈中，可以判无解。

复杂度是\(O(nm+k^3)\)

code

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 305;

const int mod = 1e9+7;

int T,n,m,tot,id[N][N],f[N][N],vis[N][N],fg,a[N][N],ans;char s[N][N];

void init()

{

	tot=fg=ans=1;

	memset(id,0,sizeof(id));

	memset(f,-1,sizeof(f));

	memset(vis,0,sizeof(vis));

	memset(a,0,sizeof(a));

}

int dfs(int i,int j)

{

	if (~f[i][j]) return f[i][j];

	if (i<1||i>n||j<1||j>m) return 1;

	if (id[i][j]) return f[i][j]=id[i][j];

	if (vis[i][j]) return f[i][j]=fg=0;vis[i][j]=1;

	if (s[i][j]=='L') f[i][j]=dfs(i,j-1);

	if (s[i][j]=='R') f[i][j]=dfs(i,j+1);

	if (s[i][j]=='U') f[i][j]=dfs(i-1,j);

	if (s[i][j]=='D') f[i][j]=dfs(i+1,j);

	vis[i][j]=0;return f[i][j];

}

void link(int u,int v){a[u][v]--;a[v][v]++;}

int main()

{

	freopen("dancestep.in","r",stdin);

	freopen("dancestep.out","w",stdout);

	scanf("%d",&T);

	while (T--)

	{

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

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

		{

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

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

				if (s[i][j]=='.') id[i][j]=++tot;

		}

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

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

				dfs(i,j);

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

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

				if (id[i][j])

				{

					link(dfs(i,j-1),id[i][j]);link(dfs(i,j+1),id[i][j]);

					link(dfs(i-1,j),id[i][j]);link(dfs(i+1,j),id[i][j]);

				}

		if (!fg) {puts("0");continue;}

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

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

				a[i][j]=(a[i][j]+mod)%mod;

		for (int i=2;i<=tot;++i)

		{

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

				while (a[j][i])

				{

					int t=a[i][i]/a[j][i];

					for (int k=i;k<=tot;++k) a[i][k]=(a[i][k]-1ll*t*a[j][k]%mod+mod)%mod,swap(a[i][k],a[j][k]);

					ans=(mod-ans)%mod;

				}

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

		}

		printf("%d\n",ans);

	}

}