Gym - 101933K ——推公式和容斥原理

84 阅读 0 评论 56 点赞

我是靠谱客的博主鳗鱼芒果，这篇文章主要介绍Gym - 101933K ——推公式和容斥原理，现在分享给大家，希望可以做个参考。

题目链接：https://vjudge.net/problem/Gym-101933K

题目大意：国王给你一个n个节点的树，有k种颜色，问正好染k种颜色的方法有多少种，前提是相邻的节点颜色不同

题解：其实仔细想想，就会发现只要求相邻节点之间不同颜色的话，和树的结构是无关的。如果只要求用k种颜色染，那么答案ans=k*(k-1)^(n-1)，那么刚好染满这k种颜色的情况，就是ans减去只染了k-1种，k-2种，k-3种.....之后剩下的。所以就可以用容斥原理，最后公式如下：

代码如下：

复制代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

/*
   使用容斥原理，直接用k种不同颜色染色，结果为f(k)=k*(k-1)^(n-1)
   那么要正好染色k中，减去其中没有涂满k种的结果就是答案
*/
typedef long long ll;
const int maxn = 2500 + 50;
const ll mod = 1000000007;
ll f[maxn];
ll f0[maxn];
ll inv[maxn];
void init()
{
	f[0] = f[1] = f0[0] = f0[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= 2505; i++) {
		f[i] = f[i - 1] * i%mod;
		f0[i] = (mod - mod / i)*f0[mod%i] % mod;
		inv[i] = inv[i - 1] * f0[i] % mod;
		
	}
}
//组合数取模
ll C(ll n, ll m)
{
	return f[n] * inv[m] % mod*inv[n - m] % mod;
}
ll pow_mod(ll a, ll p)
{
	if (p == 0)return 1;
	ll ans = pow_mod(a, p / 2);
	ans = ans * ans%mod;
	if (p % 2 == 1)ans = ans * a%mod;
	return ans;
}

int main()
{
	ll n, k;
	ios::sync_with_stdio(false);
	init();
	while (cin >> n >> k)
	{
		int temp;
		for (int i = 1; i <=n-1; i++)
			cin >> temp;
		ll ans = 0;
		int x = 1;
		for (ll i = k; i >= 1; i--)
		{
			ll add = x * i*pow_mod(i - 1, n - 1) % mod*C(k, i) % mod;
			ans = (ans + add + mod) % mod;
			x = -x;
		}
		cout << ans << endl;
	}
	return 0;
}

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

/*
   使用容斥原理，直接用k种不同颜色染色，结果为f(k)=k*(k-1)^(n-1)
   那么要正好染色k中，减去其中没有涂满k种的结果就是答案
*/
typedef long long ll;
const int maxn = 2500 + 50;
const ll mod = 1000000007;
ll f[maxn];
ll f0[maxn];
ll inv[maxn];
void init()
{
	f[0] = f[1] = f0[0] = f0[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i <= 2505; i++) {
		f[i] = f[i - 1] * i%mod;
		f0[i] = (mod - mod / i)*f0[mod%i] % mod;
		inv[i] = inv[i - 1] * f0[i] % mod;
		
	}
}
//组合数取模
ll C(ll n, ll m)
{
	return f[n] * inv[m] % mod*inv[n - m] % mod;
}
ll pow_mod(ll a, ll p)
{
	if (p == 0)return 1;
	ll ans = pow_mod(a, p / 2);
	ans = ans * ans%mod;
	if (p % 2 == 1)ans = ans * a%mod;
	return ans;
}


int main()
{
	ll n, k;
	ios::sync_with_stdio(false);
	init();
	while (cin >> n >> k)
	{
		int temp;
		for (int i = 1; i <=n-1; i++)
			cin >> temp;
		ll ans = 0;
		int x = 1;
		for (ll i = k; i >= 1; i--)
		{
			ll add = x * i*pow_mod(i - 1, n - 1) % mod*C(k, i) % mod;
			ans = (ans + add + mod) % mod;
			x = -x;
		}
		cout << ans << endl;
	}
	return 0;
}