BZOJ4011: [HNOI2015]落忆枫音(dp 乘法原理)

题意

题目链接

Sol

非常妙的一道题

设\(inder[i]\)表示\(i\)号节点的度数

首先如果是个DAG的话，可以考虑在每个点的入边中选一条边作为树形图上的边，这样\(ans = \prod_{i > 1} inder[i]\)

如果加入一条边的话，算答案的时候可能会把一些环的贡献也算进去(比如样例中\(2 - 4 - 3\))这个环

考虑减去环上的贡献，注意形成的环不止一个，准确的来说，如果加入了\(x -> y\)这条边，那么在原图中所有\(y -> x\)的路径都应该计算贡献

其中一条路径的贡献为\(\frac{ans}{S \in (y -> x) inder[S]}\)

dp一遍求出所有贡献即可

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10, mod = 1e9 + 7;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M, X, Y, inder[MAXN], inv[MAXN], t[MAXN], f[MAXN];

vector<int> v[MAXN];

void add(int &x, int y) {

	if(x + y < 0) x = x + y + mod;

	else x = (x + y >= mod ? x + y - mod : x + y);

}

int mul(int x, int y) {

	return 1ll * x * y % mod;

}

void Topsort() {

	queue<int> q;

	for(int i = 1; i <= N; i++) if(!inder[i]) q.push(i);

	while(!q.empty()) {

		int p = q.front(); q.pop(); f[p] = mul(f[p], inv[t[p]]);

		for(int i = 0; i < v[p].size(); i++) {

			int to = v[p][i];

			add(f[to], f[p]);

			if(!(--inder[to])) q.push(to);

		}

	}

}

int main() {

	N = read(); M = read(); X = read(); Y = read();

	inv[1] = 1; for(int i = 2; i <= M + 1; i++) inv[i] = mul((mod - mod / i), inv[mod % i]);

	for(int i = 1; i <= M; i++) {

		int x = read(), y = read();

		v[x].push_back(y); inder[y]++;

	}

	int ans = 1; inder[Y]++;

	for(int i = 2; i <= N; i++) ans = mul(ans, inder[i]);

	if(Y == 1) {cout << ans; return 0;}

	memcpy(t, inder, sizeof(inder));

	inder[Y]--;

	f[Y] = ans; Topsort();

	cout << (ans - f[X] + mod) % mod;

	return 0;

}