【题意&分析】
裸的无向图,求生成树个数,详见这里
注意这个mod不是质数,需要辗转相除即可
【代码】
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second #define lson now<<1 #define rson now<<1|1 typedef long long ll; const int mod=1e9; int f[102][102],id[12][12]; char p[12][12]; int n,m; void add(int x,int y) { f[x][y]--; f[y][x]--; f[x][x]++; f[y][y]++; } int ans=1; void guass(int p) { for(int i=1;i<=p;i++) { for(int j=i+1;j<=p;j++) { while(f[j][i]) { int d=f[i][i]/f[j][i]; for(int k=i;k<=p;k++) f[i][k]=(f[i][k]-1LL*d*f[j][k]%mod+mod)%mod; ans*=-1; for(int k=1;k<=p;k++) swap(f[i][k],f[j][k]); } } ans=1LL*ans*f[i][i]%mod; } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d%d",&n,&m); char s[12]; for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=m;j++) p[i][j]=s[j]; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(p[i][j]=='.') id[i][j]=++id[0][0]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(p[i][j]=='.' && p[i][j+1]=='.') add(id[i][j],id[i][j+1]); if(p[i][j]=='.' && p[i+1][j]=='.') add(id[i][j],id[i+1][j]); } guass(id[0][0]-1); printf("%d",(ans+mod)%mod); return 0; }