King's Colors 题解
link
题意：给出一个含有 \(n\) 个节点的树，以及 \(k\) 个颜色，询问有多少种方式正好用 \(k\) 个颜色给树染色，并且任意两个相邻的节点颜色不同。
拿到这道题，我刚开始考虑的是从儿子开始考虑父亲。但是这样会出现一个问题，儿子颜色重复的数量决定这个父亲的取值数量的多少。于是不好控制。
但是其实换个角度（trick），考虑从父亲开始考虑儿子，发现儿子有 \(k-1\) 种取值，则整棵树有 \(k*(k-1)^{n-1}\) 个取值，但是这样计算出来可能用不完 \(k\) 个颜色。
于是设 \(F_k=k*(k-1)^{n-1}\) 表示最多用 \(k\) 个颜色的方案数，\(f_k\) 表示恰好用 \(k\) 个颜色的方案数。可以写出：\(F_k=\sum_{i=0}^k \binom k i f_i\)，妥妥的二项式反演，得出 \(f_k=\sum_{i=0}^k(-1)^{k-i}\binom {k} {i}i*(i-1)^{n-1}\)。答案即为 \(f_k\)。
#include
#include
#include
#include
#define LL long long
using namespace std;
const int MAXN = 2505, Mod = 1e9 + 7;
int n, k;
LL jc[MAXN], inv[MAXN], ans;
LL Qpow(LL x, int y) {
LL ans = 1;
for(; y; y >>= 1) {
if(y & 1) ans = ans * x % Mod;
x = x * x % Mod;
}
return ans;
}
LL C(int x, int y) {
if(x < 0 || y < 0 || x < y) return 0;
return jc[x] * inv[y] % Mod * inv[x - y] % Mod;
}
int main() {
int x;
scanf("%d%d", &n, &k); jc[0] = 1;
for(int i = 1; i <= k; i ++) jc[i] = jc[i - 1] * i % Mod;
inv[k] = Qpow(jc[k], Mod - 2);
for(int i = k - 1; i >= 0; i --) inv[i] = inv[i + 1] * (i + 1) % Mod;
for(int i = 2; i <= n; i ++) scanf("%d", &x);
for(int i = 0; i <= k; i ++) ans = (ans + Qpow(Mod - 1, k - i) * C(k, i) % Mod * i % Mod * Qpow(i - 1, n - 1)) % Mod;
printf("%lld", ans);
return 0;
}
双倍经验
此题就是多了个 \(m\)，发现 \(m\) 很大我们尽可能不让其参与计算，所以刚开始就把 \(m\) 提出来，我们令答案为 \(ans*\binom {m} {k}\)，其中 \(ans\) 为恰好选 \(k\) 个的方案，就是上面那道题了。
值得一提的是，如果刚开始不把 \(m\) 提出来，最后可能会化为 \(f_k=\sum_{i=0}^k(-1)^{k-i}*\binom {k} {i}*\binom {m}{i}*k*(k-1)^{n-1}\)，其中求 \(\binom {m} {i}\) 会超时。这就告诉我们能减少变元就减少变元的重要性。