dp做法
时间复杂度$O(nk)$。
在树中选择任意一个叶子结点作为起点,沿着边一个点接一个点的涂色。定义$dp[i][j]$为前$i$个点使用了$j$种颜色的方案数,状态转移方程:
- 若第$i$个点选用未使用的颜色,则$dp[i][j]+=dp[i-1][j-1]*(k-j+1)$。
- 若第$i$个点选用已经使用过的颜色,则必须和$i-1$的颜色相同,若和更前面的结点颜色相同则在路径中会经过$i-1$不符合题意,则$dp[i][j]+=dp[i-1][j]$。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;
int n, k;
int u, v;
LL dp[377][377];
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i < n; i++) scanf("%d%d", &u, &v);
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
dp[i][j] += dp[i - 1][j] + dp[i - 1][j - 1] * (k - j + 1);
dp[i][j] %= mod;
}
}
for(int j = 1; j <= k; j++) {
dp[n][j] = (dp[n][j] + dp[n][j - 1]) % mod;
}
printf("%lld\n", dp[n][k]);
return 0;
}
连通块做法
时间复杂度$O(nlog_{2}{n})$,下面代码中的逆元可以进一步优化。
问题转化为把一棵树分成多个连通块,每个连通块内的结点涂相同的颜色,不同的连通块颜色不同,有多少种方案。
- 若把$n$个结点的树分成$m$个连通块,则需要删除$m-1$条边,有$C_{n-1}^{m-1}$种方案。
- $k$种颜色需要选出$m$种,有$C_{k}^{m}$种方案。
- $m$种颜色涂$m$个连通块,有$m!$种方案。
- 上面三个条件满足乘法原理,则对答案的贡献为$C_{n-1}^{m-1}*C_{k}^{m}*m!$,最后只需要枚举一下可以分成多少个连通块求和即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f; ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf; ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 5e5 + 117;
const int MAXM = 2e5 + 117;
int n, k;
int u, v;
LL fac[377], sum;
LL fast_pow(LL a, LL n) {
LL ret = 1, temp = a % mod;
while(n) {
if(n & 1) ret = ret * temp % mod;
temp = temp * temp % mod;
n >>= 1;
}
return ret;
}
LL Comb(int n, int m) {
return fac[n] * fast_pow(fac[m] * fac[n - m], mod - 2) % mod;
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i < n; i++) scanf("%d%d", &u, &v);
fac[0] = fac[1] = 1;
for(int i = 2; i < 377; i++) fac[i] = fac[i - 1] * i % mod;
if(k > n) k = n;
for(int i = 1; i <= k; i++) {
sum = (sum + Comb(n - 1, i - 1) * Comb(k, i) % mod * fac[i]) % mod;
}
printf("%lld\n", sum);
return 0;
}
版权属于:小影
本文链接:http://kindkidll.com/index.php/archives/143/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改,但请务必注明文章来源并且不可用于商业目的。
请问一下你的博客是怎么搭建的啊OωO