题目概述

有 $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;
}