【bzoj4894】天赋

Solution

　　这题的话其实，一句话题意就是求。。外向树（方向是根往叶子）。。

　　然后关于有向图的生成树计数的话，求外向树就是将度数矩阵改成入度，内向树就是改成出度

　　然后其他的一样的

　　

　　代码大概长这个样子

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=310,MOD=1e9+7;

int a[N][N],mp[N][N],d[N][N];

int n,m;

int solve(int n);

int main(){

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

#endif

    char ch;

    scanf("%d\n",&n);

    for (int i=1;i<=n;++i){

        for (int j=1;j<=n;++j){

            scanf("%c",&ch);

            mp[i][j]=ch-'0';

            if (mp[i][j]) ++d[j][j];

        }

        scanf("\n");

    }

    for (int i=1;i<=n;++i)

        for (int j=1;j<=n;++j)

            a[i][j]=(d[i][j]-mp[i][j]+MOD)%MOD;

    printf("%d\n",solve(n));

}

int solve(int n){

    int id,mark=1;

    int tmp;

    for (int i=2;i<=n;++i){

        id=i;

        for (int j=i+1;j<=n;++j)

            if (a[j][i]){id=j;break;}

        if (id!=i){

            mark=-mark;

            for (int j=2;j<=n;++j) swap(a[id][j],a[i][j]);

        }

        for (int j=i+1;j<=n;++j){

            while (a[j][i]){

                tmp=a[j][i]/a[i][i];

                for (int k=2;k<=n;++k)

                    a[j][k]=(1LL*a[j][k]+MOD-1LL*tmp*a[i][k]%MOD)%MOD;

                if (a[j][i]==0) break;

                mark=-mark;

                for (int k=2;k<=n;++k)

                    swap(a[j][k],a[i][k]);

            }

        }

    }

    int ret=mark;

    for (int i=2;i<=n;++i)

        ret=1LL*ret*a[i][i]%MOD;

    return (ret+MOD)%MOD;

}

巴特西

【bzoj4894】天赋

Solution

最新文章

热门文章