题目
题目描述
shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。
输入描述
第一行两个整数n，k代表点数和颜色数；
接下来n-1行，每行两个整数x,y表示x与y之间存在一条边；
输出描述
输出一个整数表示方案数（mod 1e9+7）。
示例1
输入
4 3
1 2
2 3
2 4
输出
39
备注
对于30%的数据，n≤10, k≤3；
对于100%的数据，n,k≤300。
题解
方法一
知识点：dfs序，线性dp。
考虑按dfn序考虑，显然后一个点要么颜色和上一个点一样，要么只能用没用过的颜色。
设 \(f_{i,j}\) 表示考虑到dfn序上第 \(i\) 个点用到了前 \(j\) 个颜色。转移方程为：
\[f_{i,j} = f_{i-1,j} + f_{i-1,j-1} \cdot (k-j+1)
\]
时间复杂度 \(O(nk)\)
空间复杂度 \(O(nk)\)
方法二
知识点：排列组合。
注意到，同一种颜色一定在一个连通块里，那么 \(i\) 个颜色需要分 \(i\) 个连通块，即需要割 \(i-1\) 条边，一共 \(\dbinom{n-1}{i-1}\) 种方案。对于每种方案，求颜色的排列方案，一共 \(\text{P}_k^i\) 。
因此，答案是 \(\displaystyle \sum_{i=1}^{\min(n,k)} \dbinom{n-1}{i-1} \text{P}_k^i\) 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
方法一
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
int f[307][307];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
f[0][0] = 1;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= k;j++) {
f[i][j] = (f[i - 1][j] + 1LL * f[i - 1][j - 1] * (k - j + 1) % P) % P;
}
}
int ans = 0;
for (int i = 1;i <= k;i++) (ans += f[n][i]) %= P;
cout << ans << '\n';
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
namespace Number_Theory {
const int N = 307;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int fact[N], invfact[N];
void init(int n) {
fact[0] = 1;
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
invfact[n] = qpow(fact[n], P - 2);
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}
}
namespace CNM {
using namespace Number_Theory;
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
}
}
using namespace CNM;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
init(max(n, k));
int ans = 0;
for (int i = 1;i <= min(n, k);i++) (ans += 1LL * C(n - 1, i - 1) * fact[k] % P * invfact[k - i] % P) %= P;
cout << ans << '\n';
return 0;
}