【BZOJ4894】天赋

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 <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

typedef long long ll;

const ll P=1000000007;

int n;

ll ans;

char str[310];

int d[310][310],lj[310][310];

ll v[310][310];

int main()

{

	scanf("%d",&n);

	int i,j,k;

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

	{

		scanf("%s",str);

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

		{

			lj[i][j]=str[j]-'0';

			if(lj[i][j])	d[j][j]++;

		}

	}

	for(i=1;i<n;i++)	for(j=1;j<n;j++)	v[i][j]=(d[i][j]-lj[i][j]+P)%P;

	for(ans=1,i=1;i<n;i++)

	{

		for(j=i;j<n;j++)	if(v[j][i])	break;

		if(j!=i)	for(ans=P-ans,k=i;k<n;k++)	swap(v[i][k],v[j][k]);

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

		{

			ll A=v[i][i],B=v[j][i],tmp,temp;

			while(B)

			{

				tmp=A/B,temp=A,A=B,B=temp%B;

				for(ans=P-ans,k=i;k<n;k++)	v[i][k]=(v[i][k]-tmp*v[j][k]%P+P)%P,swap(v[i][k],v[j][k]);

			}

		}

		ans=ans*v[i][i]%P;

	}

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

	return 0;

}

天赋