题目描述

有向图，求以1位根节点的根树个数
输入为邻接矩阵,a(i,j)为1代表i到j有边

样例

输入：
4
0 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
输出：
12

高斯消元求行列式 O（n^3）

参考https://blog.csdn.net/aoanping0730/article/details/102087144的对于BZOJ4894的解法。
构造矩阵A很简单，关键是计算去掉第一行第一列的余子式，用高斯消元。

参考文献

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define max 105//最多有几个点
using namespace std;
typedef long long lol;
int a[max][max],Mod=1000+7,n,ans;
char s[max][max];
void guass()
{
  int i,j,k;
  n--;
  ans=1;
  for (i=1;i<=n;i++)//行化简行列式
    {
      for (j=i+1;j<=n;j++)
    {
      while (a[j][i])
        {
          int t=a[i][i]/a[j][i];//碰巧目前的矩阵除了对角线元素外都是0或者-1，所以高斯消元过程中是整倍数，不然很麻烦的
          for (k=i;k<=n;k++)
        {
          a[i][k]=(a[i][k]-1ll*t*a[j][k]%Mod+Mod)%Mod;//其实你可以再任何时候对行列式的任何一个元素取模，都能保证结果模等价
          swap(a[i][k],a[j][k]);
        }
          ans*=-1;
        }
    }
      ans=1ll*ans*a[i][i]%Mod;//这里1ll的作用是在城的过程中让类型变成long long ，避免溢出。
    }
  ans=(ans+Mod)%Mod;
}
int main()
{int i,j;
char nouse;
  cin>>n;
  scanf("%c",&nouse);
  for (i=0;i<n;i++)
    {
    //注意输入格式中数字空格分开，所以：
    for(int k=0;k<n;k++){
        scanf("%c",&s[i][k]);
        scanf("%c",&nouse);
    }
    }
  for (i=0;i<n;i++)//构造出A矩阵，a(i,i)为i出度，a（i,j）为 i 到 j 的边数的相反数
    {
      for (j=0;j<n;j++)
    {
      if (s[i][j]=='1')
        a[i][j]--;
    }
      for (j=0;j<n;j++)
    {
      if (s[i][j]=='1')//这里需要注意的是有向边的方向，要弄清楚是s[i][j]=1代表的是
        a[i][i]++;
    }
    }
  guass();//计算删去第 1 行第 1 列之后的余子式，也即1 号点为根的树形图的数量。
  cout<<ans;
}