思路

给出了一个DAG,要求以1为根的外向树的个数

如果没有加边的条件,就非常好做

每个点都只保留一条入边,最后得到的一定就是一个符合条件的树了(因为给了一个DAG啊)

所以答案是\(\prod_{i=2}^nd_i\)

加上一条边时候,可能会出现环的情况,要把它去掉

假设环中的点是\(a_1,a_2,a_3,\dots,a_k\),去掉的情况数就是\(\frac{\prod_{i=2}^nd_i}{\prod_{i=1}^kd_{a_i}}\)(除了环上的点之外其他随便选,成环只有环上的点每个点都选择环上的边的一种情况)

对后面的式子在原DAG上直接拓扑求一下就好了

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
const int MOD = 1000000007;
int n,m,x,y;
int u[100100<<1],v[100100<<1],fir[100100],nxt[100100<<1],d[100100],cnt,f[100100],ans,d_t[100100];
void addedge(int ui,int vi){
++cnt;
u[cnt]=ui;
v[cnt]=vi;
d[vi]++;
d_t[vi]++;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
int pow(int a,int b){
int ans=1;
while(b){
if(b&1)
ans=(ans*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return ans;
}
queue<int> q;
void topu(void){
f[y]=ans;
for(int i=1;i<=n;i++)
if(!d_t[i])
q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
f[x]=(f[x]*pow(d[x],MOD-2))%MOD;
for(int i=fir[x];i;i=nxt[i]){
f[v[i]]=(f[v[i]]+f[x])%MOD;
d_t[v[i]]--;
if(!d_t[v[i]])
q.push(v[i]);
}
} }
signed main(){
scanf("%lld %lld %lld %lld",&n,&m,&x,&y);
d[y]++;
for(int i=1;i<=m;i++){
int a,b;
scanf("%lld %lld",&a,&b);
addedge(a,b);
}
ans=1;
for(int i=2;i<=n;i++)
ans=(ans*d[i])%MOD;
if(y==1){
printf("%lld\n",ans);
return 0;
}
topu();
printf("%lld\n",(ans-f[x]+MOD)%MOD);
return 0;
}
05-17 11:57