[HNOI2015]落忆枫音

设每个点入度是\(d_i\)，如果不加边，答案是

意思是我们给每个点选一个父亲

然后我们加了一条边，最后如果还这么统计，那么有一些不合法的图是\(y,\dots,x\)形成了一个环，考虑把所有环的方案减掉。

考虑枚举环上的点集\(S\)，答案为

意思是环上的点钦定父亲，其他的点照旧统计

这个方案数可以dp，设\(dp_i\)表示\(i,\dots,x\)形成的环的答案

那么初始值有

然后每个点加入环的时候除上自己的入度，也就是

然后这个dp直接在topo图上记搜就可以了

Code:

#include <cstdio>

#include <cctype>

#include <cstring>

const int mod=1e9+7;

const int N=1e5+10;

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

int head[N],to[N<<1],Next[N<<1],cnt;

void addedge(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

#define mul(a,b) (1ll*(a)*(b)%mod)

int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}

int dp[N],d[N];

int dfs(int now)

{

	if(~dp[now]) return dp[now];

	dp[now]=0;

	for(int v,i=head[now];i;i=Next[i])

		dfs(v=to[i]),dp[now]=add(dp[now],dp[v]);

	dp[now]=mul(dp[now],qp(d[now],mod-2));

	return dp[now];

}

int main()

{

	int n,m,y,x;

	read(n),read(m),read(y),read(x);

	memset(dp,-1,sizeof dp);

	dp[y]=1;

	for(int u,v,i=1;i<=m;i++)

	{

		read(u),read(v);

		addedge(u,v);

		++d[v];

	}

	int ans=1;

	for(int i=2;i<=n;i++)

	{

		if(i==x) ans=mul(ans,d[i]+1);

		else ans=mul(ans,d[i]);

		dp[y]=mul(dp[y],d[i]);

	}

	if(x==1) return printf("%d\n",ans),0;

	dp[y]=mul(dp[y],qp(d[y],mod-2));

	ans=add(ans,mod-dfs(x));

	printf("%d\n",ans);

	return 0;

}

2019.2.25