BZOJ4894:天赋(矩阵树定理)

2023-08-12 18:16:58

Description

小明有许多潜在的天赋，他希望学习这些天赋来变得更强。正如许多游戏中一样，小明也有n种潜在的天赋，但有一些天赋必须是要有前置天赋才能够学习得到的。

也就是说，有一些天赋必须是要在学习了另一个天赋的条件下才能学习的。比如，要想学会"开炮"，必须先学会"开枪"。

一项天赋可能有多个前置天赋，但只需习得其中一个就可以学习这一项天赋。

上帝不想为难小明，于是小明天生就已经习得了1号天赋-----"打架"。于是小明想知道学习完这n种天赋的方案数，答案对1,000,000,007取模。

Input

第一行一个整数n。

接下来是一个n*n的01矩阵，第i行第j列为1表示习得天赋j的一个前置天赋为i。

数据保证第一列和主对角线全为0。

n<=300

Output

第一行一个整数，问题所求的方案数。

Sample Input

8
01111111
00101001
01010111
01001111
01110101
01110011
01111100
01110110

Sample Output

72373

Solution

终于来填矩阵树的坑了……

其实也没啥难的，就是高斯消元解个行列式就完了……（行列式的性质可以看这里）

这个题其实是让你求以$1$为根的外向树生成树个数。

无向图生成树：度数矩阵-邻接矩阵

有向图外向生成树：入度矩阵-邻接矩阵

有向图内向生成树：出度矩阵-邻接矩阵

把这个矩阵删掉一行一列然后求出的行列式的值就是生成树个数。

注意有向图的生成树需要删除根所在的行列来计算行列式。

Code

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #define N (309)

 #define LL long long

 #define MOD (1000000007)

 using namespace std;

 LL n,f[N][N];

 char s[N];

 LL inv(LL a)

 {

     LL ans=,b=MOD-;

     while (b)

     {

         if (b&) ans=ans*a%MOD;

         a=a*a%MOD; b>>=;

     }

     return ans;

 }

 void Gauss(LL n)

 {

     int w=,ans=;

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

     {

         int num=i;

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

             if (abs(f[j][i])>abs(f[num][i])) num=j;

         if (num!=i) swap(f[num],f[i]), w=-w;

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

         {

             int t=f[j][i]*inv(f[i][i])%MOD;

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

                 f[j][k]=(f[j][k]-t*f[i][k])%MOD;

         }

     }

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

         ans=ans*f[i][i]%MOD;

     ans=(ans*w%MOD+MOD)%MOD;

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

 }

 int main()

 {

     scanf("%lld",&n);

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

     {

         scanf("%s",s);

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

             f[i][j]-=s[j]-'';

     }

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

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

             if (i!=j && f[i][j]==-) f[j][j]++;

     Gauss(n-);

 }

码农公寓