首页 > 代码库 > Bzoj4894 天赋

Bzoj4894 天赋

2024-09-22 11:55:58   206人阅读

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 16

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

HINT

 

Source

By 佚名上传

 

图论 基尔霍夫矩阵 高斯消元

把“点了一个前置技能(或一个前置相同的同级技能)，接着点当前技能”看成一条有向边，那么我们要求的就是这个有向图的树形图的数量。

 

（度娘告诉我）有向图也可以用矩阵树定理搞。

敲完以后跑样例，怎么调答案都是0

输出矩阵看了一下，发现最左边一列全是0，然后注意到树形图的根固定了是1，也许这导致矩阵实际上少了一个元？

暴力把矩阵往左上平移一单位，再求出行列式，发现就是答案。

 

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mod=1e9+7; 9 const int mxn=305;10 int f[mxn][mxn];11 int n;12 char s[mxn];13 int ksm(int a,int k){14     int res=1;15     while(k){16         if(k&1)res=(LL)res*a%mod;17         a=(LL)a*a%mod;18         k>>=1;19     }20     return res;21 }22 int solve(int n){23     int i,j,k,F=1;24     for(i=1;i<=n;i++){25         int p=i;26         for(j=i;j<=n;j++)if(f[j][i]){p=i;break;}27         if(p!=i){for(j=1;j<=n;j++)swap(f[p][j],f[i][j]); F=-F;}28         for(j=i+1;j<=n;j++){29             LL inv=(LL)f[j][i]*ksm(f[i][i],mod-2)%mod;30             for(k=i;k<=n;k++){31                 f[j][k]=((LL)f[j][k]-inv*(LL)f[i][k]%mod+mod)%mod;32             }33         }34     }35     int res=F;36     for(i=1;i<=n;i++)res=(LL)res*f[i][i]%mod;37     if(res<0)res+=mod;38     return res;39 }40 int main(){41     int i,j;42     scanf("%d",&n);43     for(i=1;i<=n;i++){44         scanf("%s",s+1);45         for(j=1;j<=n;j++){46             if(s[j]==‘1‘){47                 f[j][j]++;48                 f[i][j]--;49             }50         }51     }52     for(i=1;i<=n;i++)53         for(j=1;j<=n;j++)54             f[i][j]=f[i+1][j+1];55     LL ans=solve(n-1);56     printf("%lld\n",ans);57     return 0;58 }

 

Bzoj4894 天赋


联系
我们