Solution - P3244 [HNOI2015]落忆枫音

Posted on Edited on

P3244 [HNOI2015]落忆枫音

idea

dpdp ，数学

solution

设 ind[i]ind[i] 表示 ii 节点的入度。如果图是一个 DAGDAG ，答案为 ∏i=2nind[i]\prod_{i=2}^n ind[i] 。

我们容斥一下，假设图是个 DAGDAG ，求出 ans=∏i=2nind[i]ans = \prod_{i=2}^n ind[i] ，然后再减去有环的情况。

注意：虽然只添加一条边，但是图上会出现多个环！

那么我们枚举环 SS ，需要减掉的答案就是

∑Sans∏i∈Sind[i]\sum_S \frac{ans}{\prod_{i\in S} ind[i]}

特别地，如果添加的边 st→edst \to ed 中的 ed=1ed = 1 ，答案就是 ansans ！如果不特判，会被扣十分!

我们用 dpdp 来求这个值。设

g[cur]=∑S is one of ed→curans∏i∈Sind[i]g[cur] = \sum_{S\ is\ one\ of\ ed\to cur} \frac{ans}{\prod_{i\in S} ind[i]}

那么

g[to]=1ind[to]∑The edge (cur,to) existsg[cur]g[to] = \frac{1}{ind[to]}\sum_{The\ edge\ (cur,to)\ exists} g[cur]

用拓扑排序或者记忆化搜索都行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
const int N=1e5+5,M=2e5+5,MOD=1e9+7;
int n,m,ind[N],st,ed,d[N],g[N];
vector<int> G[N];
inline int ny(int a){
	int s=1,b=MOD-2;
	while (b){
		if (b&1) s=(LL)s*a%MOD;
		a=(LL)a*a%MOD,b>>=1;
	}
	return s;
}
signed main(){
	cin>>n>>m>>st>>ed;++ind[ed];
	for (int i=1;i<=m;++i){
		int x,y;cin>>x>>y;
		G[x].pb(y);
		++ind[y],++d[y];
	}
	int ans=1;
	for (int i=2;i<=n;++i){
		ans=(LL)ans*ind[i]%MOD;
	}
	if (ed==1) return cout<<ans,0;
	queue<int> q;
	if (ind[ed]) g[ed]=(LL)ans*ny(ind[ed])%MOD;
	for (int i=1;i<=n;++i){
		if (!d[i]) q.push(i);
	}
	while (!q.empty()){
		int cur=q.front();q.pop();
		for (int i=0;i<(int)G[cur].size();++i){
			int to=G[cur][i];
			--d[to];
			if (!d[to]) q.push(to);
			g[to]=(g[to]+(LL)g[cur]*ny(ind[to])%MOD)%MOD;
		}
	}
	cout<<(ans-g[st]+MOD)%MOD;
	return 0;
}