https://www.luogu.com.cn/problem/P3244
题目简述
有一个\(n\)个点，\(m\)条边的DAG，现在向这个图中添加一条\(l到r\)的有向边，问有多少种以1为根的外向树方案。
数据范围
\(1\le n\le 10^5,n-1 \le m \le min(2*10^5,\frac{n(n-1)}{2})\)
\(deg_i表示第i个点的入度，不考虑环的总方案数为\prod_{i\ne 1}deg_i\)
\(考虑经过环的方案数，因为加入边之前原图为DAG，所以每个环一定包含新加入的边，所以环经过的点就是r到l路径上的所有点\)
\(所以经过环的方案数即为\sum_{S}\prod_{i\ne s'}deg_i\)
\(S表示r到l路径上的点集，s'为点集中的某个点\)
\(如果直接求，显然O(n^2)，会TLE，但是这个值其实可以dp求出\)
\(转移式为f_i=\sum_{i->j}\frac{f_j}{deg_i}\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int deg[100009],dp[100009],ans1,head[100009],v[100009];
int n,m,st,ed,top,ans2;
int qpow(int a,int k)
{
int nowans=1;
while(k)
{
if(k&1)
nowans=(nowans*a)%mod;
a=(a*a)%mod;
k>>=1;
}
return nowans;
}
struct bian
{
int to,lt;
}b[200009];
void mkb(int l,int r)
{
top++;
b[top]=(bian){r,head[l]};
head[l]=top;
}
void dfs(int x)
{
if(x==ed)
{
return;
}
if(v[x])
return;
v[x]=1;
for(int t=head[x];t;t=b[t].lt)
{
int y=b[t].to;
dfs(y);
dp[x]+=dp[y];
dp[x]%=mod;
}
dp[x]=(dp[x]*qpow(deg[x],mod-2))%mod;
}
signed main()
{
cin>>n>>m>>st>>ed;
for(int i=1;i<=m;i++)
{
int l,r;
cin>>l>>r;
mkb(r,l);
deg[r]++;
}
ans1=1;
deg[1]=1;
for(int i=1;i<=n;i++)
ans1=(ans1*deg[i])%mod;
dp[ed]=(ans1*qpow(deg[ed],mod-2))%mod;
dfs(st);
ans2=1;
for(int i=1;i<=n;i++)
if(i!=ed)
ans2=(ans2*deg[i])%mod;
else
ans2=(ans2*(deg[i]+1))%mod;
if(ed!=1&&st!=ed)
cout<<((ans2-dp[st])%mod+mod)%mod;
else
cout<<ans1;
return 0;
}