走进矩阵树定理--「CodePlus 2017 12 月赛」白金元首与独舞

n,m<=200，n*m的方阵，有ULRD表示在这个格子时下一步要走到哪里，有一些待决策的格子用.表示，可以填ULRD任意一个，问有多少种填法使得从每个格子出发都能走出这个方阵，答案取模。保证未确定的格子<=300。

。。。一脸懵逼地写了原本30实际20的暴力然后跪着啃了下论文

然而什么都没啃懂不如结论记下来：

首先矩阵行列式的定义：一个n*n的矩阵，行列式值为$\sum_{b是n的一个排列} \ \ \ \ \ ( (-1)^{b的逆序对数} \ \ \ \ \ * \prod_{i=1}^{n} A_{i,b_i})$

矩阵A行列式的性质：

|A|=|A的转置|

|AB|=|A||B|

|A|+|B|=|A和B的某一行加起来其他不变的矩阵|

交换两行得B，|B|=-|A|，因为每次计算一个排列时逆序对数都相差1。

A的某行乘个x得B，|B|=x|A|。

A的某行乘某个数加到另一行上得B，|B|=|A|。由第三条可得。

每行每列和为0的矩阵行列式为0。

由四五六条可用高斯消元计算行列式。

基尔霍夫矩阵：

无向图：矩阵对角线上是度数，其他如果对应边存在就是-1，不然就是0。

有向图：矩阵对角线上是入度，其他如果对应边存在就是-1，不然就是0。

矩阵树定理：一个无向图的基尔霍夫矩阵的任意一个n-1阶的子矩阵，即删掉了第i行和第i列，的行列式是这个图的生成树个数。

一个有向图以点i为根的生成树个数是基尔霍夫矩阵去掉第i行和第i列剩下的矩阵的行列式。

如果图为多图，作如下修改：

当$i \neq j$而有重边时，把邻接矩阵的1改成$i$，$j$间的边数；

当$i = j$而有自环时，自环不可能出现在生成树中，统计度数时记得忽略之。

嗯然后就是这道题。

首先，如果在外界虚拟一个节点，把所有指出去的格子都指向它，把所有确定格子向指向的点连边，可得一个有向图。

然后，待确定的点向四个方向都连边，求这个图以外界点为根的反向的树形图即可。为什么呢，首先确定的格子的边一定会选到，因为每个格子只有一条出边，不然他就和其他点断掉了；其次那些待确定的格子为了形成树，只会在四个方向里选一个。

嗯这样只能拿50分。

可以发现那些已经确定的点是多余的，可以缩掉。也就是给所有待确定格子编号，外界点编号0，然后预处理他往上下左右走能遇到的第一个有编号的格子，朝他们连边即可。

然后就大功告成了。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<stdlib.h>

 //#include<queue>

 #include<math.h>

 //#include<time.h>

 //#include<iostream>

 using namespace std;

 int n,m,K,T;

 const int mod=1e9+;

 #define maxn 311

 int pos[maxn][maxn],who[maxn][maxn],place[maxn][]; char mp[maxn][maxn];

 int powmod(int a,int b)

 {

     int ans=;

     while (b)

     {

         if (b&) ans=1ll*ans*a%mod;

         a=1ll*a*a%mod;

         b>>=;

     }

     return ans;

 }

 struct Mat

 {

     int num[maxn][maxn];

     void clear() {memset(num,,sizeof(num));}

 }mat;

 int gauss()

 {

     int ans=;

     for (int i=;i<=K;i++)

     {

         int id=i;

         for (int j=i+;j<=K;j++) if (fabs(mat.num[j][i])>fabs(mat.num[id][i])) id=j;

         if (id!=i)

         {

             ans=1ll*ans*(mod-)%mod;

             for (int j=i;j<=K;j++) {int t=mat.num[i][j]; mat.num[i][j]=mat.num[id][j]; mat.num[id][j]=t;}

         }

         int tmp=powmod(mat.num[i][i],mod-);

         for (int j=i+;j<=K;j++)

             for (int k=K;k>=i;k--)

                 mat.num[j][k]-=mat.num[i][k]*1ll*mat.num[j][i]%mod*tmp%mod,

                 mat.num[j][k]+=mat.num[j][k]<?mod:;

     }

     for (int i=;i<=K;i++) ans=1ll*ans*mat.num[i][i]%mod;

     return ans;

 }

 int vis[maxn][maxn],Time; bool die;

 void dfs(int x,int y)

 {

     if (mp[x][y]=='.') return;

     if (vis[x][y])

     {

         if (pos[x][y]==-) die=;

         return;

     }

     vis[x][y]=;

     int tx=x,ty=y;

     if (mp[x][y]=='U') x--;

     else if (mp[x][y]=='D') x++;

     else if (mp[x][y]=='L') y--;

     else if (mp[x][y]=='R') y++;

     if (x< || x>n || y< || y>m) pos[tx][ty]=;

     else pos[tx][ty]=-,dfs(x,y),pos[tx][ty]=pos[x][y];

 }

 int check(int x,int y)

 {

     if (x< || x>n || y< || y>m) return ;

     return pos[x][y];

 }

 int main()

 {

     scanf("%d",&T);

 while (T--)

 {

     scanf("%d%d",&n,&m); K=; Time=; die=;

     memset(vis,,sizeof(vis));

     memset(pos,,sizeof(pos));

     for (int i=;i<=n;i++) scanf("%s",mp[i]+);

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

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

             if (mp[i][j]=='.') pos[i][j]=++K;

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

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

             if (mp[i][j]!='.') dfs(i,j);

     if (die) {puts(""); continue;}

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

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

             if (mp[i][j]=='.')

             {

                 int nx=i,ny=j,now=pos[i][j];

                 nx++; place[now][]=check(nx,ny); nx--;

                 nx--; place[now][]=check(nx,ny); nx++;

                 ny++; place[now][]=check(nx,ny); ny--;

                 ny--; place[now][]=check(nx,ny); ny++;

             }

     mat.clear();

     for (int i=;i<=K;i++)

     {

         for (int j=;j<;j++) mat.num[place[i][j]][i]--;

         mat.num[i][i]+=;

     }

     for (int i=;i<=K;i++)

         for (int j=;j<=K;j++)

             if (mat.num[i][j]<) mat.num[i][j]+=mod;

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

 }

     return ;

 }

巴特西

走进矩阵树定理--「CodePlus 2017 12 月赛」白金元首与独舞

最新文章

热门文章