md这题和矩阵树定理没半毛钱关系qwq
首先先不考虑有环,一个(DAG)个外向树个数为(prod_{i=2}^{n}idg_i()就是(indegree_i)),因为外向树每个点入度为一,对于一个点有入度个父亲可选,然后乘法原理起来就是答案
现在可能加一条边会有环,那么答案可以考虑总方案减不合法方案,不合法的有环方案就是环内的点连好了,然后剩下的点贡献方案,设(s)是个环,那么方案为(sum_{s}prod_{i otin s}idg_i=sum_{s}frac{prod_{i=2}^{n}idg_i}{prod_{iin s}idg_i}=prod_{i=2}^{n}idg_isum_{s}frac{1}{prod_{iin s}idg_i})
后面那个东西,因为加了边(x ightarrow y),所以一条(y)到(x)可以确定一个环,那么以(y)为初始状态,可拓扑排序一遍dp出来方案
注意(y=1)的情况
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=1e5+10,mod=1e9+7;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],hd[N],dg[N],idg[N],tot;
void add(int x,int y){++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot,++dg[y];}
int n,m,u,v,f[N],inv[N];
queue<int> q;
int main()
{
n=rd(),m=rd(),u=rd(),v=rd();
for(int i=1;i<=m;++i)
{
int x=rd(),y=rd();
add(x,y);
}
int ans=1;
for(int i=2;i<=n;++i) ans=1ll*ans*(dg[i]+(v==i))%mod;
if(v!=u&&v!=1)
{
memcpy(idg,dg,sizeof(dg));
inv[0]=inv[1]=1;
for(int i=2;i<=n+1;++i) inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
f[v]=1,q.push(1);
while(!q.empty())
{
int x=q.front();
q.pop();
f[x]=1ll*f[x]*inv[dg[x]+(x==v)]%mod;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
f[y]=(f[y]+f[x])%mod,--idg[y];
if(!idg[y]) q.push(y);
}
}
ans=1ll*ans*(1-f[u]+mod)%mod;
}
printf("%d
",ans);
return 0;
}