E. Darth Vader and Tree - 题解
比赛与标签
比赛: Codeforces Round 291 (Div. 2) 标签: dp, matrices 难度: *2200
喵喵，这道题在说什么呀？
主人，这道题是关于一棵无限大的树的计数问题哦！(ฅ'ω'ฅ)
想象一下，我们有一棵从根节点开始的无限延伸的树。每个节点都像妈妈猫一样，有 n 个可爱的孩子喵~ 连接父节点和它第 i 个孩子的边的长度是 d_i。
我们的任务是，给定一个最大距离 x，数一数在这棵树里，从根节点出发，距离不超过 x 的节点一共有多少个。因为答案可能会非常非常大，所以我们需要对 10^9 + 7 取模。
输入格式：
- 第一行是两个整数
n和x，分别是每个节点的孩子数量和最大距离。 - 第二行是
n个整数d_i，表示连接父节点和第i个孩子的边的长度。
输出格式：
- 一个整数，表示距离根节点不超过
x的节点总数，结果要模10^9 + 7哦。
一起动动脑筋，找到答案吧！
看到这种在树上数路径和计数的问题，我们的第一反应通常是动态规划（DP）呢，喵~
Step 1: 朴素的DP想法
我们可以定义一个数组 f[i]，表示在树中，距离根节点正好为 i 的节点有多少个。
基础情况:
f[0] = 1，因为距离为 0 的节点只有根节点自己呀。状态转移: 怎么计算
f[i]呢？一个节点如果距离根为i，那它的父节点距离根一定是i - d_k，其中d_k是连接它和父节点的边的长度。所以，我们可以通过所有子节点的情况来推导：f[i] = ∑ (从父节点走长为 d_k 的边到达的节点数)为了方便计算，我们可以先预处理一下，用一个
freq[d]数组记录下长度为d的边有多少种（即有多少个d_i等于d）。这样，状态转移方程就变成：f[i] = ∑_{d=1}^{100} freq[d] * f[i-d]这个式子的意思是，对于每一种长度为d的边，它都可以从任何一个距离为i-d的节点延伸出来，形成一个新的距离为i的节点。
题目要求的是距离不超过 x 的节点总数，所以我们再定义一个 g[i]，表示距离根节点不超过 i 的节点总数。 g[i] = f[0] + f[1] + ... + f[i] 很显然，g[i] = g[i-1] + f[i]。我们的最终答案就是 g[x] 啦！
Step 2: 发现问题并升级思路
这个DP思路看起来很完美，但是看看数据范围，x 最大可以到 10^9！如果一步一步从 i=1算到 x，肯定会超时的说！(｡>ㅅ<｡)
当DP的转移是线性的，而状态数又特别大时，就是矩阵快速幂大显身手的时候了！
我们可以把DP的递推关系变成矩阵乘法的形式。
确定状态向量: 我们的目标是求
f[t]和g[t]。f[t]的计算依赖于f[t-1], f[t-2], ..., f[t-100]（因为d_i最大是100）。所以，我们的状态向量需要包含这些历史信息。同时，为了计算g[t]，我们还需要g[t-1]。 因此，我们可以构建一个大小为 101 的状态向量S_t：S_t = [f[t-1], f[t-2], ..., f[t-100], g[t-1]]^T（注意，这里为了方便，我们把f的下标倒着排，T表示转置）构建转移矩阵: 我们需要找到一个
101 x 101的转移矩阵A，使得S_{t+1} = A * S_t。S_{t+1} = [f[t], f[t-1], ..., f[t-99], g[t]]^T让我们来一行一行地构建A：- 计算
f[t]:f[t] = ∑_{d=1}^{100} freq[d] * f[t-d]。这一项对应新状态向量的第一行。它等于freq[1]*f[t-1] + freq[2]*f[t-2] + ...。所以A的第一行的前 100 个元素就是freq[1], freq[2], ..., freq[100]。 - 计算
f[t-1], f[t-2], ...: 新状态的f[t-1]就是旧状态的f[t-1]，新状态的f[t-2]就是旧状态的f[t-2]... 咦不对，新状态的第k项f[t-k+1]其实就是旧状态的第k-1项f[t-(k-1)]。这形成了一个“向下平移”的效果。在矩阵中，这表现为在主对角线的下方形成一条为1的斜线。即A[i][i-1] = 1fori=1..99。 - 计算
g[t]:g[t] = g[t-1] + f[t] = g[t-1] + ∑_{d=1}^{100} freq[d] * f[t-d]。这一项对应新状态向量的最后一行。所以A的最后一行的前 100 个元素也是freq[1], ..., freq[100]，并且对应g[t-1]的位置（第101列）是1。
- 计算
最终计算:
- 我们先用朴素DP计算出
x <= 100的所有f[i]和g[i]值。这作为我们矩阵加速的初始状态。 - 如果
x <= 100，直接输出g[x]就好啦。 - 如果
x > 100，我们构建初始状态向量S_{100} = [f[99], f[98], ..., f[0], g[99]]^T。 - 我们想求的是
S_{x+1}，它等于A^(x-99) * S_{100}。 - 用矩阵快速幂计算出
M = A^(x-99)。 - 然后计算
Result = M * S_{100}。 Result向量的最后一个元素就是我们梦寐以求的g[x]啦！
- 我们先用朴素DP计算出
这样，我们就把 O(x) 的复杂度降到了 O(D^3 * log(x))，其中 D 是边长的最大值（这里是100），可以轻松通过此题了喵~
代码实现喵~
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int maxd = 100;
// 定义一个矩阵结构体，方便进行矩阵运算喵
struct Matrix {
int n, m;
vector<vector<ll>> data;
Matrix(int n, int m) : n(n), m(m) {
data = vector<vector<ll>>(n, vector<ll>(m, 0));
}
// 创建一个单位矩阵
static Matrix identity(int n) {
Matrix I(n, n);
for (int i = 0; i < n; i++)
I.data[i][i] = 1;
return I;
}
// 矩阵乘法，记得要取模哦
Matrix operator*(const Matrix& other) const {
Matrix res(n, other.m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < other.m; j++) {
ll sum = 0;
for (int k = 0; k < m; k++) {
sum = (sum + (data[i][k] * other.data[k][j]) % mod) % mod;
}
res.data[i][j] = sum;
}
}
return res;
}
};
// 矩阵快速幂，和普通快速幂原理一样，只是把乘法换成了矩阵乘法
Matrix matrix_power(Matrix base, ll power) {
Matrix res = Matrix::identity(base.n);
while (power) {
if (power & 1)
res = res * base;
base = base * base;
power /= 2;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
ll x;
cin >> n >> x;
vector<ll> d(n);
vector<ll> freq(101, 0); // freq[i] 记录长度为 i 的边有多少种
for (int i = 0; i < n; i++) {
cin >> d[i];
if (d[i] <= maxd)
freq[d[i]]++;
}
// f[i]: 距离根恰好为 i 的节点数
vector<ll> f(101, 0);
// g[i]: 距离根不超过 i 的节点数
vector<ll> g(101, 0);
// DP 预处理
f[0] = 1; // 根节点
g[0] = 1;
for (int t = 1; t <= 100; t++) {
// 计算 f[t]
for (int d_val = 1; d_val <= 100; d_val++) {
if (t >= d_val) {
f[t] = (f[t] + freq[d_val] * f[t - d_val]) % mod;
}
}
// 计算 g[t]
g[t] = (g[t - 1] + f[t]) % mod;
}
// 如果 x 比较小，直接用DP的结果就好啦
if (x <= 100) {
cout << g[x] % mod << endl;
return 0;
}
// --- 矩阵快速幂部分 ---
// 构建初始状态向量 base (大小 101x1)
// base = [f[99], f[98], ..., f[0], g[99]]^T
Matrix base(101, 1);
for (int i = 0; i < 100; i++) {
base.data[i][0] = f[99 - i];
}
base.data[100][0] = g[99];
// 构建转移矩阵 A (大小 101x101)
Matrix A(101, 101);
// 第一行，用于计算新的 f[t]
for (int j = 0; j < 100; j++) {
A.data[0][j] = freq[j + 1];
}
// 中间的99行，用于将 f[t-1]...f[t-99] 向下平移
for (int i = 1; i < 100; i++) {
A.data[i][i - 1] = 1;
}
// 最后一行，用于计算新的 g[t] = g[t-1] + f[t]
for (int j = 0; j < 100; j++) {
A.data[100][j] = freq[j + 1];
}
A.data[100][100] = 1;
// 计算 A^(x-99)
Matrix M = matrix_power(A, x - 99);
// 得到最终状态向量
Matrix result = M * base;
// 最终答案是结果向量的最后一个元素，即 g[x]
ll ans = result.data[100][0] % mod;
if (ans < 0) ans += mod; // 确保结果是正数
cout << ans << endl;
return 0;
}复杂度分析的说
- 时间复杂度: O(max_d^2 + (max_d+1)^3 * log(x)) 的说。
- 前面的DP预处理部分是
O(max_d * max_d)，因为max_d=100，所以这是个常数时间。 - 矩阵快速幂是主要部分。矩阵大小是
(max_d+1) x (max_d+1)，我们记为D x D。一次矩阵乘法是O(D^3)，快速幂需要进行O(log(x))次乘法。所以这部分是O(D^3 * log(x))。 - 总的来说，是
O((max_d+1)^3 * log(x))。
- 前面的DP预处理部分是
- 空间复杂度: O((max_d+1)^2) 的说。
- 我们需要存储DP数组
f和g，大小为O(max_d)。 - 还需要存储转移矩阵和中间结果矩阵，大小都是
O((max_d+1)^2)。所以空间复杂度由矩阵大小决定。
- 我们需要存储DP数组
知识点与总结喵~
这道题是一道非常经典的 DP + 矩阵快速幂 优化问题，通过它我们可以学到很多东西呐！
- 线性递推的识别: 当你发现一个DP问题的状态转移方程是线性的（即新状态是旧状态的线性组合），并且需要计算的项数非常大时，就要立刻想到矩阵快速幂！
- 状态向量的构建: 关键在于如何把递推关系塞进矩阵里。你需要确定一个状态向量，它必须包含计算下一步所需的所有信息。在这个问题里，就是
f的前100项和g的当前项。 - 转移矩阵的构造: 根据状态转移方程，一行一行地确定转移矩阵
A的每一项。这需要细心和对矩阵乘法有清晰的理解。 - 分段处理: 对于
x较小的情况，直接用DP求解更简单高效。这种“小范围打表/DP，大范围上高级算法”的思路在很多题目中都很有用哦。
总之，遇到线性递推和巨大的 n，不要害怕，祭出矩阵快速幂这个大杀器就对啦！希望这篇题解能帮到你，加油喵~ (๑•̀ㅂ•́)و✧