首页 > 代码库 > Bzoj4894 天赋
Bzoj4894 天赋
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
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 天赋
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。