Java教程

P3244[HNOI2015]落忆枫音(计数dp + 组合数学 + DAG）

本文主要是介绍P3244[HNOI2015]落忆枫音(计数dp + 组合数学 + DAG），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

P3244 [HNOI2015]落忆枫音

题目传送门

题目大意 ： 略

题目分析 ：

  • [\(1\)]：我们发现原图是一个 \(DAG\)，那么我们很容易知道，若在一个 \(DAG\) 中找一棵生成树，那么总方案数为 \(\prod_{i = 1}^n deg_i\),因为对于每个点我们都有 \(deg_i\) 那么多种方案，又因为他是一个 \(DAG\) 所以根据乘法原理，我们就可以得出这个公式。

  • [\(2\)]：我们考虑用 \(dp\) 来解决这个问题（感觉计数类的不是 \(dp\) 就是组合数学的公式，也可能是二者的结合体），我们如何进行求解呢，我们发现若我们正着进行求解，我们怎样设计呢。发现这个问题很难继续进行了。但我们很容易知道知道总的方案数啊！！所以就可以正难则反了。

  • [\(3\)]：加入一条边之后，可能会出现环，但也可能不会，后一种情况是我们最希望出现的，接下来我们考虑如何对于第一种情况求解。我们只需要求出有环的方案数即可。我们假设出现了一个环，且环上有 \(k\) 个点为：\(a_1,a_2,a_3,...,a_k\)。我们可以钦定形成了这个环，那么形成这个环的方案数就是 \(\frac{总方案数}{环上点度数的乘积}\),转成公式就是 \(\frac{\begin{matrix} \prod{i = 1}^n deg_i \end{matrix} }{\prod{j = 1}^k deg_{a_j}}\)

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int M = 1e6 + 7;
int n , m , x , y;
vector<int> e[M];
int sum;
int deg[M];
int f[M];
int vis[M];
int Pow(int a , int b) {
	int ans = 1; 
	while(b) {
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
void dfs(int u) {
	if(vis[u]) return;
	vis[u] = 1;
	if(u == y) {f[u] = sum * Pow(deg[u] , mod - 2) % mod; return;}
	for(auto i : e[u]) {
		dfs(i);
		f[u] = (f[u] + f[i]) % mod;
	}
	f[u] = (f[u] * Pow(deg[u] , mod - 2) % mod ) % mod;
}
signed main () {
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> n >> m >> x >> y;
	for(int i = 1; i <= m; ++ i) {
		int u , v; cin >> u >> v;
		e[v].push_back(u);
		deg[v] ++;	
	}
	deg[1] ++;
	int ans = 1; 
	sum = 1;
	for(int i = 1; i <= n; ++ i) {
		if(i == y) ans = ans * (deg[i] + 1) % mod;
		else ans = ans * deg[i] % mod;
		sum = sum * deg[i] % mod;
	}	
	dfs(x);
	cout << ((ans + mod - f[x]) % mod) ;
}

[========]

本题完结！

这篇关于P3244[HNOI2015]落忆枫音(计数dp + 组合数学 + DAG）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航