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;
}

最后

以上就是鳗鱼芒果为你收集整理的Gym - 101933K ——推公式和容斥原理的全部内容，希望文章能够帮你解决Gym - 101933K ——推公式和容斥原理所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。