GYM 101933K（二项式反演、排列组合）

方法一

设\(f_i\)为最多使用\(i\)种颜色的涂色方案，\(g_i\)为恰好只使用\(i\)种颜色的涂色方案。可知此题答案为\(g_k\)。
根据排列组合的知识不难得到\(f_k = \sum_{i=0}^k{C_k^i*g_i}\)。
根据二项式反演的式子 or 容斥原理，有\(g_k = \sum_{i = 0}^k{(-1)^{k-i}*C_k^i*f_i}\)，这时只要有\(f_i\)我们就可以累加得到最终答案，看题面考虑\(f_i\)的现实意义，根有\(i\)种可选，往下涂每个点有\(i-1\)种可选（因为是树形的，所以子节点涂色只要和父亲不同即可），故\(f_i = i * (i - 1)^{n - 1}\)。

#include <cstdio>

const int mod = 1e9 + 7;

int n, k, ans;

int C[2505][2505], f[2505];

int ksm(int a, int b) {

	int res = 1;

	for (; b; b >>= 1) {

		if (b & 1)	res = 1LL * res * a % mod;

		a = 1LL * a * a % mod;

	}

	return res;

}

void Pre() {

	for (int i = 0; i <= k; i++) {

		f[i] = 1LL * i * ksm(i - 1, n - 1) % mod;

		C[i][i] = C[i][0] = 1;

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

			C[i][j] = (1LL * C[i - 1][j] + C[i - 1][j - 1]) % mod;

		}

	}

}

int main() {

	scanf("%d %d", &n, &k);

	for (int i = 1, x; i < n; i++)

		scanf("%d", &x);

	Pre();

	for (int i = 0; i <= k; i++) {

		int a = (k - i) % 2 ? -1 : 1;

		int tmp = (1LL * a * C[k][i] % mod * f[i] % mod + mod) % mod;

		ans = (ans + tmp) % mod;

	}

	return !printf("%d\n", ans);

}

方法二

假设\(f(n,k)\)是答案。
染一个叶子节点，有两种情况：1.它的颜色是独一无二的：\(k*f(n-1,k-1)\)种染色方式；2.有别的节点和它颜色一样（则它不和父亲相同）：\((k-1)*f(n-1,k)\)种染色方式。因此将这两种加起来就是答案。

#include <cstdio>

#include <cstring>

typedef long long ll;

const int mod = 1e9 + 7;

int n, k;

int dp[2505][2505];

int f(int n, int k) {

    if (n == 1) return k == 1 ? 1 : 0;

    if (dp[n][k] != -1)    return dp[n][k];

    return dp[n][k] = ((ll)k * f(n - 1, k - 1) % mod + (ll)(k - 1) * f(n - 1, k) % mod) % mod;

}

int main() {

    scanf("%d %d", &n, &k);

    for (int i = 1, x; i < n; i++) {

        scanf("%d", &x);

    }

    memset(dp, -1, sizeof dp);

    return !printf("%d\n", f(n, k));

}

方法二是直接染色了，也可以先求出模式数，再乘\(k!\)使其染色，详解我写在cf 140E

#include <cstdio>

typedef long long ll;

const int mod = 1e9 + 7;

const int maxn = 2510;

int n, k;

ll f[maxn][maxn];

int main() {

    scanf("%d %d", &n, &k);

    f[0][0] = 1;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= i; j++)

            f[i][j] = (f[i - 1][j - 1] + f[i - 1][j] * (j - 1)) % mod;

    ll ans = f[n][k];

    for (int i = 1; i <= k; i++)

        ans = ans * i % mod;

    return !printf("%d\n", (int)ans);

}

巴特西

GYM 101933K（二项式反演、排列组合）

方法一

方法二

最新文章

热门文章