自动搬运

查看原文

来自洛谷，原作者为

	litble 苟……苟活者在淡红的血色中，会依稀看见微茫的希望（AFO)

搬运于2025-08-24 21:46:53，当前版本为作者最后更新于2018-03-21 10:09:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

组合计数+dp

对于DAG来说，考虑每个点的父亲，令du(x)表示x的入度，则答案是$\prod du(i)$

现在加了一条边，可能是环了，我们就要考虑从$\prod du(i)$里减去成环的情况。假设一个大小为$k$的环含有节点$a_1,a_2...a_k$，除了这个环以外的节点的父亲随意选取，那么要减去的值就是

记新加的边为(s,t)

考虑用dp完成，令g(x)表示从t到x的路径上，上面式子里的这个值，那么$g(x)=\frac{1}{du(x)}(\sum g(y))$（y可达x）。由于原图是DAG，直接在原图上记忆化搜索即可。

答案就是$\sum du(i) - g(s)$了。

#include<bits/stdc++.h>
using namespace std;
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
#define RI register int
const int mod=1000000007,N=100005,M=200005;
int n,m,xx,yy,ans=1,tot,dsum=1;
int h[N],ne[M],to[M],du[N],g[N],vis[N];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
int ksm(int x,int y) {
	int re=1;
	for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
	return re;
}
void dfs(int x) {
	if(vis[x]) return;
	vis[x]=1;
	if(x==yy) {g[x]=1LL*dsum*ksm(du[x],mod-2)%mod;return;}
	for(int i=h[x];i;i=ne[i])
		dfs(to[i]),g[x]=(g[x]+g[to[i]])%mod;
	g[x]=1LL*g[x]*ksm(du[x],mod-2)%mod;
}
int main()
{
	int x,y;
	n=read(),m=read(),xx=read(),yy=read();
	for(RI i=1;i<=m;++i)
		x=read(),y=read(),add(y,x),++du[y];
	++du[1];
	for(RI i=1;i<=n;++i) {
		if(i==yy) ans=1LL*(du[i]+1)*ans%mod;
		else ans=1LL*du[i]*ans%mod;
		dsum=1LL*du[i]*dsum%mod;
	}
	dfs(xx);
	ans=(ans+mod-g[xx])%mod;
	printf("%d\n",ans);
    return 0;
}