天赋 HYSBZ – 4894 (生成树计数+辗转相除高斯消元)

天赋 HYSBZ - 4894 (生成树计数+辗转相除高斯消元)
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说天赋 HYSBZ - 4894 (生成树计数+辗转相除高斯消元),希望能够帮助大家进步!!!

小明有许多潜在的天赋,他希望学习这些天赋来变得更强。正如许多游戏中一样,小明也有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 Output72373 Hint

 




 

 

其实就是问你这个有向图的生成树个数。方法依旧是利用矩阵树定理,只不过与无向图不同的是,要将度数矩阵改成入度矩阵或出度矩阵,分别对应外向树和内向树。还有删掉的那行和那列必须是根的那行那列。

 

A为邻接矩阵,D为度数矩阵,则基尔霍夫(Kirchhoff)

矩阵即为:K=D−A。具体实现中,记 a 为Kirchhoff矩阵,则若存在 E(u,v),

则 a[u][u]++ ,a[v][v]++,a[u][v]−−,a[v][u]−− 。即a[i][i]

 为 ii 点的度数, a[i][j] 为 i,ji,j之间边的条数的相反数。

 

剩余系下没有除法,所以使用辗转相除高斯消元

 

gauss之前要把数组内所有的数全变成mod意义下的正数

 




#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]++;
        }
    }
    int ff=1;
    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(ff*=-1,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(v[j][i])
            {
                ll t=v[i][i]/v[j][i];
               // tmp=A/B,temp=A,A=B,B=temp%B;
                for(ff*=-1,k=i;k<n;k++)
                    v[i][k]=(v[i][k]-t*v[j][k]%P+P)%P,
                    swap(v[i][k],v[j][k]);
            }
        }
        ans=ans*v[i][i]%P;
    }
    if(ff==-1 ) ans *=-1;
    ans %=P ;ans += P ;ans %= P;
    printf("%lld\n",ans);
    return 0;
}

 

转载于:https://www.cnblogs.com/zhangbuang/p/10919720.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29797

发表评论