menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[矩阵树定理]BZOJ4894【天赋】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $n$ 个技能,每个技能有一些前置技能,现在 $1$ 技能已学习,求学完所有技能的方案数。

解题报告

矩阵树定理求有向图中外向树和内向树的个数:

  • 外向树:边从父亲到儿子的有向树

    • 度数矩阵为每个点的入度,邻接矩阵 $i,j$ 是 $i\to j$ 的边的个数。
  • 内向树:边从儿子到父亲的有向树(其实可以看成边全反向之后求外向树个数)

    • 度数矩阵为每个点的出度,邻接矩阵 $i,j$ 是 $j\to i$ 的边的个数。

然后就是 $n-1$ 阶主子式必须消去根所在的那一行那一列。

证明?我不会啊!这道题直接套外向树就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300,MOD=1e9+7;

int n,a[maxn+5][maxn+5];

inline char getdig() {char ch=getchar();while (!isdigit(ch)) ch=getchar();return ch;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Det(int n,int ans=1){
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=(a[i][j]+MOD)%MOD;
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++)
            if (a[j][i]) {if (i!=j) {for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]);ans=-ans;}break;}
        for (int j=i+1;j<=n;j++)
            while (a[j][i]){
                int t=a[j][i]/a[i][i];for (int k=i;k<=n;k++) AMOD(a[j][k],MOD-(LL)a[i][k]*t%MOD);
                if (!a[j][i]) break;for (int k=i;k<=n;k++) swap(a[i][k],a[j][k]);ans=-ans;
            }
    }for (int i=1;i<=n;i++) ans=(LL)ans*a[i][i]%MOD;ans=(ans+MOD)%MOD;return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=n;i;i--) for (int j=n;j;j--) if (getdig()=='1') a[i][j]--,a[j][j]++;
    printf("%d\n",Det(n-1));return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up