题解：小妖精繁殖世代的最大化与矩阵快速幂

---

问题分析

本题模拟小妖精的繁殖过程，要求计算在时间 $T$ 内能达到的最大世代数。关键点：

• 初始有 $N$ 只小妖（每种一个），视为第1代
• 第 $i$ 种小妖：成熟时间 $Y_i$，产 $K_i$ 个蛋，第 $j$ 个蛋孵化时间 $H_{i,j}$，孵化出类型 $G_{i,j}$ 的小妖
• 只考虑在时间 $T$ 内已孵化的小妖
• 求最大世代数

问题本质：在时间限制 $T$ 内，通过繁殖链能达到的最大"深度"。

---

核心观察

1. 时间约束下的繁殖

从一只类型 $i$ 的小妖出生开始：

• 需要 $Y_i$ 年成熟
• 产蛋后，第 $j$ 个蛋需要 $H_{i,j}$ 年孵化
• 所以从 $i$ 出生到它的第 $j$ 个孩子 $G_{i,j}$ 出生的总时间为：$Y_i + H_{i,j}$

2. 问题转化为图论

构建有向图：

• 节点：小妖类型 $1 \dots N$
• 边 $i \to G_{i,j}$，权重 $w = Y_i + H_{i,j}$ 表示从父代出生到子代出生所需时间

那么问题转化为：从初始节点（所有类型，时间为0）出发，在总时间 $\le T$ 内能走的最大步数（边数）。

3. 最大步数 vs 最短时间

我们需要最大化步数（世代数），同时满足总时间 $\le T$。这是一个在时间约束下最大化路径长度的问题。

等价于：对于每个可能的步数 $k$，求从初始状态出发走 $k$ 步所需的最短时间。然后找到最大的 $k$ 使得最短时间 $\le T$。

---

算法框架

第一步：构建转移矩阵

定义矩阵 $M$，$M[i][j]$ 表示从类型 $i$ 的小妖出生到类型 $j$ 的小妖出生所需的最短时间（通过一代繁殖）。

初始化：

$$M[i][j] = \min_{1 \le t \le K_i} \{ Y_i + H_{i,t} \mid G_{i,t} = j \} $$

如果不存在这样的边，$M[i][j] = \infty$。

第二步：矩阵快速幂

$M^k$ 表示走 $k$ 步的最短时间矩阵，其中 $(M^k)[i][j]$ 表示从 $i$ 出发，经过 $k$ 代到达 $j$ 的最短总时间。

使用矩阵快速幂计算 $M^{2^t}$（$t=0,1,\dots,50$，因为 $2^{50} > 10^{15}$）。

矩阵乘法定义为：

$$(C = A \times B) \Rightarrow C[i][j] = \min_k \{ A[i][k] + B[k][j] \} $$

这是经典的min-plus矩阵乘法，适用于最短路问题。

第三步：二进制分解

从高位到低位检查每个二进制位：

• 当前已走步数为 $ans$，对应时间矩阵为 $L$（从初始状态出发）
• 检查是否能再走 $2^t$ 步：计算 $N = L \times M^{2^t}$
• 如果 $N$ 中任意类型的最短时间 $\le T$，则可行，更新 $ans$ 和 $L$

初始 $L$ 满足 $L[0][i] = 0$（表示初始时所有类型时间为0）。

第四步：答案计算

最终 $ans$ 即为最大世代数。

---

关键实现细节

min-plus矩阵乘法

matrix operator *(const matrix &b)const {
    matrix t;
    t.init();
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            if (c[i][j] < inf)
                for (int k = 0; k <= n; k++)
                    if (b.c[j][k] < inf)
                        Min(t.c[i][k], c[i][j] + b.c[j][k]);
    return t;
}

二进制分解

ll ans = 0;
for (int t = 50; t >= 0; t--) {
    nxt = las * f[t];  // f[t] = M^(2^t)
    ll mi = inf;
    for (int i = 1; i <= n; i++)
        Min(mi, nxt.c[0][i]);  // 检查所有类型
    if (mi <= T) {
        ans += (1ll << t);
        las = nxt;  // 更新当前状态
    }
}

初始化

初始矩阵 $L$ 满足 $L[0][i] = 0$，表示初始时每个类型有一只0时间出生的小妖。

---

复杂度分析

• 矩阵大小：$N \le 100$，矩阵 $101 \times 101$（包含第0行用于初始状态）
• 矩阵乘法：$O(N^3) \approx 10^6$
• 快速幂预处理：$O(\log T \times N^3) \approx 50 \times 10^6 = 5 \times 10^7$
• 二进制分解：$O(\log T \times N^3)$
• 总复杂度：约 $10^8$ 量级，可接受

---

正确性证明

1. 矩阵乘法的正确性

min-plus矩阵乘法满足： $(A \times B)[i][j] = \min_k \{A[i][k] + B[k][j]\}$

对于繁殖问题：

• $A[i][k]$：从 $i$ 到 $k$ 的最短时间
• $B[k][j]$：从 $k$ 到 $j$ 的最短时间
• 求和表示连续繁殖的总时间
• 取最小值得到最短路径

因此 $M^k$ 确实表示 $k$ 步繁殖的最短时间。

2. 二进制分解的正确性

设当前已走 $ans$ 步，对应时间矩阵 $L$。 检查是否能再走 $2^t$ 步：计算 $L \times M^{2^t}$。

如果结果中存在时间 $\le T$ 的路径，说明可行。由于 $2^t$ 是2的幂，可以贪心地从高位到低位尝试。

3. 初始状态处理

第0行表示"虚拟初始状态"，$L[0][i] = 0$ 表示初始时每个类型有一只0时刻出生的小妖。这样乘法结果 $L \times M^k$ 的第0行就是所有类型经过 $k$ 代后的最短时间。

---

样例分析

样例2

• 类型1：成熟10年，产1个蛋孵化5年 → 孩子类型1，总15年
• 类型2：成熟5年，产1个蛋孵化5年 → 孩子类型1，总10年

二进制分解：

• 初始 $ans=0$
• 尝试 $2^5=32$ 步：时间太长，不行
• ...
• 最终 $ans=3$：对应路径 类型1(0年) → 类型1(15年) → 类型1(30年) → 类型1(45年>42) 不行 但可以有其他路径达到3代且在42年内

---

总结

本题是一道矩阵快速幂与最优化的综合题目，主要考察：

1. 问题转化能力：将繁殖过程转化为图论最短路问题
2. min-plus矩阵：使用min-plus代数处理最短时间
3. 矩阵快速幂：高效计算多步转移
4. 二进制分解：在时间约束下最大化步数

算法的核心创新在于：

• 使用min-plus矩阵表示繁殖的时间关系
• 通过矩阵快速幂计算任意步数的最短时间
• 利用二进制分解在时间约束下寻找最大步数

这种"矩阵快速幂+二进制分解"的方法是解决带约束的步数最大化问题的强大工具，尤其适用于时间范围极大（$T \le 10^{15}$）的情况。