BZOJ 4894: 天赋 有向图生成树计数

4894: 天赋

Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 56  Solved: 49 [Submit][Status][Discuss]

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

太久不做矩阵树定理。。。欧几里得都不会打了。。。

邻接矩阵竟然直接加上了度数矩阵。。。智商捉急。。

好好好 来说题解。。。

不就是裸的有根有向图生成树计数吗。。。

矩阵树定理。。真是。。。啥也不会了。。。

推荐一篇好文章（其实我也没读）

「from CommonAnts」Matrix-Tree 定理相关

#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<set> #include<map> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(int x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=310,mod=int(1e9)+7; int a[N][N]; int det(int n) { register int f=1,i,j,k,x,y,t,res=1; for(i=1;i<=n;++i) { for(j=i+1;j<=n;++j) { x=a[i][i],y=a[j][i]; while(y) { t=x/y;x%=y;swap(x,y); for(k=i;k<=n;++k)a[i][k]=(a[i][k]-(1ll*a[j][k]*t%mod))%mod; for(k=i;k<=n;++k)swap(a[i][k],a[j][k]); f=-f; } } if(!a[i][i])return 0; res=1ll*res*a[i][i]%mod; } if(f==-1)res=-res; return (res%mod+mod)%mod; } char s[N]; int main() { int n=read(); register int i,j; for(i=1;i<=n;++i) { scanf("%s",s+1); for(j=1;j<=n;++j)if(s[j]=='1') {a[n-i+1][n-j+1]=-1;a[n-j+1][n-j+1]++;} } print(det(n-1));puts(""); return 0; } /* 8 01111111 00101001 01010111 01001111 01110101 01110011 01111100 01110110 72373 */