问题分析

我们有一个 $(L+1) \times n$ 的有向图，顶点用 $(u, v)$ 表示，其中 $0 \le u \le L$，$1 \le v \le n$。图的边权规则为：

• 若 $u_1 < u_2$，则从 $(u_1, v_1)$ 到 $(u_2, v_2)$ 有 $w(v_1, v_2)$ 条边
• 否则没有边

白兔从 $(0, x)$ 出发，每次沿任意出边跳到下一顶点，可在任意时刻停止（到达 $u = L$ 时必须停止）。要求对每个 $t \in [0, k)$，计算满足以下条件的舞曲数量（模 $p$）：

• 舞曲长度 $m \bmod k = t$
• 最终停在顶点 $(u, y)$（$u$ 任意）

核心思路

1. 矩阵建模

设 $A$ 是 $n \times n$ 的边权矩阵，$A_{ij} = w(i, j)$。从 $(0, x)$ 到任意 $(u, y)$ 的路径数为 $(A^u)_{x,y}$。由于可以在任意 $u \le L$ 停止，总方案数为：

$$F = \sum_{u=0}^L A^u$$

我们需要 $F_{x,y}$ 中路径长度 $m$（即 $u$）模 $k$ 为 $t$ 的部分。

2. 单位根反演

利用单位根反演公式：

$$[m \bmod k = t] = \frac{1}{k} \sum_{j=0}^{k-1} \omega^{-jt} \omega^{jm} $$

其中 $\omega$ 是模 $p$ 的 $k$ 次单位根（由 $k \mid p-1$ 保证存在）。

于是：

$$\text{Ans}_t = \frac{1}{k} \sum_{j=0}^{k-1} \omega^{-jt} \left( \sum_{u=0}^L \omega^{ju} A^u \right)_{x,y} $$

3. 矩阵求和处理

令 $M_j = I + \omega^j A$，则 $B_j = M_j^L$ 包含了从 $u=0$ 到 $u=L$ 的所有路径，因为每一步可以选择"停止"或"继续"。

算法实现

1. 寻找单位根

通过分解 $p-1$ 的质因数，找到原根 $g$，然后计算 $\omega = g^{(p-1)/k}$ 作为 $k$ 次单位根。

2. 计算 $f[j]$

根据 $n$ 的大小分别处理：

• $n = 1$：直接数论计算 $(1 + \omega^j A)^L$
• $n = 2, 3$：构造矩阵 $M_j = I + \omega^j A$，通过矩阵快速幂计算 $M_j^L$

3. 单位根反演

使用 MTT（拆系数FFT）实现卷积计算：

• 将数字拆分为低位和高位两部分
• 在复数域进行 FFT
• 合并结果并取模

4. 主流程

1. 寻找单位根 $\omega$
2. 对每个 $j = 0 \dots k-1$ 计算 $f[j] = (M_j^L)_{x,y}$
3. 预处理 $\omega$ 的幂次
4. 通过单位根反演计算每个 $t$ 的答案

关键优化

1. 矩阵快速幂：利用 $n \leq 3$ 的特点，手写 $2\times 2$ 和 $3\times 3$ 矩阵运算
2. MTT 优化：避免直接高精度计算，通过复数域 FFT 计算模 $p$ 卷积
3. 预处理：预先计算 $\omega$ 的幂次，减少重复计算

复杂度分析

• 矩阵计算：$O(k \cdot n^3 \log L)$
• 卷积计算：$O(k \log k)$
• 空间复杂度：$O(k)$

总结

本题是一个结合了图论、矩阵和生成函数的综合问题，主要考察以下知识点：

1. 矩阵建模：将图上的路径计数问题转化为矩阵幂次和
2. 单位根反演：处理模 $k$ 余数约束的经典技巧
3. 原根与单位根：在模意义下进行离散傅里叶变换
4. MTT 算法：解决任意模数下的卷积计算
5. 矩阵快速幂：高效计算矩阵的高次幂