题意
给你一个(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
",ans);
}
}