【BZOJ4894】天赋（矩阵树定理）

题面

BZOJ

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

题解

还是矩阵树模板题啊。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 303

#define MOD 1000000007

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int a[MAX][MAX],n;

char g[MAX];

int main()

{

	n=read();

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

	{

		scanf("%s",g+1);

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

			if(g[j]=='1')a[i][j]--,a[j][j]++;

	}

	int ans=1;

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

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

			while(a[j][i])

			{

				int t=a[i][i]/a[j][i];

				for(int k=i;k<=n;++k)a[i][k]=(a[i][k]-1ll*a[j][k]*t%MOD+MOD)%MOD,swap(a[i][k],a[j][k]);

				ans*=-1;

			}

	for(int i=2;i<=n;++i)ans=1ll*ans*a[i][i]%MOD;

	printf("%d\n",(ans+MOD)%MOD);

	return 0;

}