BZOJ4894 天赋

天赋"/>

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

这题求的是有向图的生成数计数

转化一下，邻接矩阵只计出边，度数矩阵只计入边

但是不同的是，去掉i行i列求的是以i为根的有向生成树

所以只能去掉第1行第1列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long lol;
 8 int a[301][301],Mod=1e9+7,n,ans;
 9 char s[301][301];
10 void guass()
11 {int i,j,k;
12   n--;
13   ans=1;
14   for (i=1;i<=n;i++)
15     {
16       for (j=1;j<=n;j++)
17     {
18       a[i][j]=(a[i][j]+Mod)%Mod;
19     }
20     }
21   for (i=1;i<=n;i++)
22     {
23       for (j=i+1;j<=n;j++)
24     {
25       while (a[j][i])
26         {
27           int t=a[i][i]/a[j][i];
28           for (k=i;k<=n;k++)
29         {
30           a[i][k]=(a[i][k]-1ll*t*a[j][k]%Mod+Mod)%Mod;
31           swap(a[i][k],a[j][k]);
32         }
33           ans*=-1;
34         }
35     }
36       ans=1ll*ans*a[i][i]%Mod;
37     }
38   ans=(ans+Mod)%Mod;
39 }
40 int main()
41 {int i,j;
42   cin>>n;
43   for (i=0;i<n;i++)
44     {
45       scanf("%s",s[i]);
46     }
47   for (i=0;i<n;i++)
48     {
49       for (j=0;j<n;j++)
50     {
51       if (s[i][j]=='1')
52         a[i][j]--;
53     }
54       for (j=0;j<n;j++)
55     {
56       if (s[j][i]=='1')
57         a[i][i]++;
58     }
59     }
60   guass();
61   cout<<ans;
62 }

 

转载于:.html