树上组合计数
主要来讲一讲树上的一些有关排列组合计数的问题。
树上拓扑序
给定一棵包含 \(n\) 个节点，以 \(1\) 为根的树。求树上拓扑序个数，即求有多少种排列方式，满足每个节点的父亲排在他前面。
\(1 \le n \le 10^6\)
显然，如果没有任何限制，整棵树的方案数为 \(n!\)。
对于一棵以 \(x\) 为节点的子树，假设它有 \(size_x\) 个节点，那么这 \(size_x\) 个节点中，\(x\) 需要排在最前面，所以只有 \(\dfrac{1}{size_x}\) 种选择。每颗子树的答案相互独立，因此总答案为 \(\dfrac{n!}{\prod_{i=1}^nsize_i}\)。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 1e6 + 3;
const int Mod = 1e9 + 7;
struct E {
int p, y;
} e[kmax << 1];
int n;
int h[kmax], ec;
int siz[kmax];
long long f[kmax];
long long fac[kmax], inv[kmax];
long long res = 1;
long long Pow(long long x, long long y) {
long long r = 1;
for (; y; y >>= 1) {
if (y & 1) r = r * x % Mod;
x = x * x % Mod;
}
return r;
}
void Addedge(int x, int y) {
e[++ec] = {h[x], y};
h[x] = ec;
}
void Dfs(int x) {
siz[x] = 1;
for (int i = h[x]; i; i = e[i].p) {
int y = e[i].y;
Dfs(y);
siz[x] += siz[y]; // 求子树大小
}
}
int main() {
scanf("%d", &n);
for (int i = 1, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
Addedge(y, x); // 连向父亲节点
}
for (int i = 1; i <= n; i++) {
if (siz[i]) continue;
Dfs(i);
}
res = fac[n];
for (int i = 1; i <= n; i++) {
res = res * Pow(siz[i], Mod - 2) % Mod; // 记录答案
}
printf("%lld\n", res);
return 0;
}
F - Distributing Integers
在上一题的基础上加入换根dp。
考虑当前的根为 \(x\)，需要将当前的根转移到 \(son\) 上，记 \(x\) 的答案为 \(res_x\)。
那么原来的 \(siz_x\) 由 \(n\) 变成了 \(n-siz_{son}\)，原来的 \(siz_{son}\) 变成了 \(n\)。
所以 \(res_{son} = res_x \times siz_{son} \div n \times n \div (n-siz_{son})=res_s\times siz_{son} \div (n-siz_{son})\)。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 1e6 + 3;
const int Mod = 1e9 + 7;
struct E {
int p, y;
} e[kmax << 1];
int n;
int h[kmax], ec;
int siz[kmax];
long long f[kmax];
long long fac[kmax], inv[kmax];
long long res = 1, ans[kmax];
long long Pow(long long x, long long y) {
long long r = 1;
for (; y; y >>= 1) {
if (y & 1) r = r * x % Mod;
x = x * x % Mod;
}
return r;
}
void Addedge(int x, int y) {
e[++ec] = {h[x], y};
h[x] = ec;
}
void Dfs(int x, int fa) {
siz[x] = 1;
for (int i = h[x]; i; i = e[i].p) {
int y = e[i].y;
if (y == fa) continue;
Dfs(y, x);
siz[x] += siz[y];
}
}
void Dfss(int x, int fa) {
for (int i = h[x]; i; i = e[i].p) {
int y = e[i].y;
if (y == fa) continue;
long long ress = ans[x];
ress = ress * Pow(n - siz[y], Mod - 2) % Mod * siz[y] % Mod; // 换根
ans[y] = ress;
Dfss(y, x);
}
}
int main() {
scanf("%d", &n);
for (int i = 1, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
Addedge(x, y);
Addedge(y, x);
}
Dfs(1, 0);
res = fac[n];
for (int i = 1; i <= n; i++) {
res = res * Pow(siz[i], Mod - 2) % Mod;
}
ans[1] = res; // 求出1的答案
Dfss(1, 0); // 遍历整棵树，求出其他答案
for (int i = 1; i <= n; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
树上染色
shy 有一颗 \(n\) 个节点的树，现在要用 \(k\) 种不同颜色的染料给树染色。
一个染色方案是合法的，当且仅当对于所有相同颜色的点对 \((x,y)\)，\(x\) 到 \(y\) 的路径上的所有点的颜色都要与 \(x\) 和 \(y\) 相同。即对于每种颜色，要么没染，要么染成该颜色的节点只形成一个连通块。
请统计染色方案数，对 \(10^9+7\) 取模。
\(1 \le k \le n \le 10^5\)
其实与树都没有关系。
我们先枚举颜色数量，假设我们使用 \(s\) 种颜色染，那么我们需要从 \(n-1\) 条边中选出 \(s-1\) 条断开，这是 \(C(n-1,s-1)\) 的，然后我们要从 \(k\) 种颜色中选出 \(s\) 种并分配给 \(s\) 个连通块，是 \(A(k,s)\) 的。
总答案为 \(\sum_{i=1}^kC(n-1,i-1)\times A(k,i)\)，要记得取模。
代码:
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 1e5 + 3;
const int Mod = 1e9 + 7;
struct E {
int p, y;
} e[kmax << 1];
int n, k;
int h[kmax], ec;
long long fac[kmax], inv[kmax];
long long res;
void Addedge(int x, int y) {
e[++ec] = {h[x], y};
h[x] = ec;
}
long long Pow(long long x, long long y) {
long long r = 1;
for (; y; y >>= 1) {
if (y & 1) r = r * x % Mod;
x = x * x % Mod;
}
return r;
}
void Init() {
fac[0] = inv[0] = 1;
// 求阶乘
for (int i = 1; i < kmax; i++) {
fac[i] = fac[i - 1] * i % Mod;
}
// 求逆元
inv[kmax - 1] = Pow(fac[kmax - 1], Mod - 2);
for (int i = kmax - 2; i; i--) {
inv[i] = inv[i + 1] * (i + 1) % Mod;
}
}
long long C(long long x, long long y) { //组合
return fac[x] * inv[y] % Mod * inv[x - y] % Mod;
}
long long A(long long x, long long y) { //排列
return fac[x] * inv[x - y] % Mod;
}
int main() {
Init();
cin >> n >> k;
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
Addedge(x, y);
Addedge(y, x);
}
for (int i = 1; i <= k; i++) {
res = (res + C(n - 1, i - 1) * A(k, i) % Mod) % Mod; // 计算，取模
}
printf("%lld\n", res);
return 0;
}
树上连通块
给定一棵包含 \(n\) 个节点的树，求出每个节点所在的连通块数量，对 \(10^9+7\) 取模。
\(1\le n \le 10^6\)
先来考虑以 \(1\) 为整棵树的根，定义 \(f_i\) 表示在以 \(i\) 为根的子树内，\(i\) 必选的连通块个数。
那么易得 \(f_i = \prod_{j\in Son_i}f_j+1\)，即选该子树和不选该子树。
其他节点的答案，我们可以用换根实现。
当从点 \(x\) 转移到 \(son\) 时， \(son\) 的答案需要加上 \(x\) 这一棵子树的答案，即 \(x\) 的其他子树。
用逆元是可以被卡的，所以我们要换一种思路。
考虑计算一棵子树的时候，记录好子树前缀和后缀的答案，除去一棵子树时取前缀与后缀即可。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 1e6 + 3;
const int Mod = 1e9 + 7;
int n;
long long f[kmax], res[kmax];
vector<int> e[kmax];
void Dfs(int x, int fa) {
f[x] = 1;
for (int y : e[x]) {
if (y == fa) continue;
Dfs(y, x);
f[x] = f[x] * (f[y] + 1) % Mod;
}
}
void Dfss(int x, int fa, long long v) {
res[x] = f[x] * (v + 1) % Mod;
long long p[e[x].size() + 2], s[e[x].size() + 2];
p[0] = s[e[x].size() + 1] = 1;
for (int i = 1; i <= e[x].size(); i++) { // 计算前缀
int y = e[x][i - 1];
if (y == fa) {
p[i] = p[i - 1];
} else {
p[i] = p[i - 1] * (f[y] + 1) % Mod;
}
}
for (int i = e[x].size(); i; i--) { // 计算后缀
int y = e[x][i - 1];
if (y == fa) {
s[i] = s[i + 1];
} else {
s[i] = s[i + 1] * (f[y] + 1) % Mod;
}
}
for (int i = 1; i <= e[x].size(); i++) {
int y = e[x][i - 1];
if (y == fa) continue;
Dfss(y, x, (v + 1) * p[i - 1] % Mod * s[i + 1] % Mod); // 取前缀和后缀
}
}
int main() {
cin >> n;
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
Dfs(1, 0); // 先算出1的答案
Dfss(1, 0, 0); // 换根计算
for (int i = 1; i <= n; i++) {
cout << res[i] << '\n';
}
return 0;
}
完结撒花 \ / \ / \ /