要点
- 设\(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);
}