直接构图

无向图生成树计数。运用矩阵树定理

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;const LL mod=1e9;LL MOD(LL x){ return ((x%mod)+mod)%mod;}int z;LL kf[110][110];int id[20][20];LL gethls(){ LL ans=1,tp=1; for(int i=2;i<=z;i++) { for(int j=i+1;j<=z;j++) { int x=i,y=j; while(kf[y][i]!=0) { LL t=kf[x][i]/kf[y][i]; for(int k=i;k<=z;k++) kf[x][k]=MOD(kf[x][k]-kf[y][k]*t); swap(x,y); } if(x!=i) { for(int k=2;k<=z;k++) swap(kf[x][k],kf[y][k]); tp=0-tp; } } ans=MOD(ans*kf[i][i]); } ans=MOD(ans*tp); return ans;}char ss[20];int main(){ freopen("data.in","r",stdin); freopen("1.out","w",stdout); int n,m; scanf("%d%d",&n,&m); memset(id,-1,sizeof(id)); memset(kf,0,sizeof(kf)); for(int i=1;i<=n;i++) { scanf("%s",ss+1); for(int j=1;j<=m;j++) { if(ss[j]=='.') { id[i][j]=++z; if(id[i][j-1]!=-1) { int x=id[i][j-1],y=z; kf[x][y]--;kf[y][x]--; kf[x][x]++;kf[y][y]++; } if(id[i-1][j]!=-1) { int x=id[i-1][j],y=z; kf[x][y]--;kf[y][x]--; kf[x][x]++;kf[y][y]++; } } } } for(int i=1;i<=z;i++) for(int j=1;j<=z;j++)MOD(kf[i][j]); printf("%lld\n",gethls()); return 0;}