1644：【例 4】佳佳的 Fibonacci

题目描述

佳佳对数学，尤其对数列十分感兴趣。在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。例如用 $S(n)$ 表示 Fibonacci 前 $n$ 项和 $\bmod m$ 的值，即 $S(n)=(F_1+F_2+...+F_n) \bmod m$，其中 $F_1=F_2=1, F_i=F_{i-1}+F_{i-2}$。可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。用 $T(n)=(F_1+2F_2+3F_3+...+nF_n) \bmod m$ 表示 Fibonacci 数列前 $n$ 项变形后的和 $\bmod m$ 的值。

现在佳佳告诉你了一个 $n$ 和 $m$，请求出 $T(n)$ 的值。

输入格式

输入数据包括一行，两个用空格隔开的整数 $n,m$。

输出格式

仅一行，$T(n)$ 的值。

样例

样例输入 #1

5 5

样例输出 #1

1

样例解释 #1

• Fibonacci 数列前 $5$ 项：$F_1=1, F_2=1, F_3=2, F_4=3, F_5=5$。
• $T(5) = 1 \times 1 + 2 \times 1 + 3 \times 2 + 4 \times 3 + 5 \times 5 = 1 + 2 + 6 + 12 + 25 = 46$。
• $46 \bmod 5 = 1$。

数据范围

• 对于 $30\%$ 的数据，$1 \le n \le 1000$；
• 对于 $60\%$ 的数据，$1 \le m \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n, m \le 2^{31}-1$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：$n$ 很大，需要矩阵快速幂加速。我们需要计算 $T(n) = \sum_{i=1}^n i \cdot F_i$。

设 $S(n) = \sum_{i=1}^n F_i$，$T(n) = \sum_{i=1}^n i \cdot F_i$。

考虑递推关系：

• $F_{n+1} = F_n + F_{n-1}$
• $S_{n+1} = S_n + F_{n+1}$
• $T_{n+1} = T_n + (n+1) F_{n+1}$

我们希望将 $T_{n+1}$ 表示为 $T_n, F_n, F_{n-1}, S_n, n$ 等的线性组合。但 $n$ 本身在变化，所以需要将 $n$ 也纳入状态向量。

定义状态向量：

$$\mathbf{X}_n = \begin{bmatrix} F_n \\ F_{n-1} \\ S_n \\ T_n \\ n \\ 1 \end{bmatrix}$$

注意：$F_{n-1}$ 是必要的，因为递推需要前两项。$n$ 和 $1$ 是为了构造 $(n+1)$。

我们希望找到转移矩阵 $A$，使得 $\mathbf{X}_{n+1} = A \cdot \mathbf{X}_n$。

写出 $\mathbf{X}_{n+1}$ 各分量：

1. $F_{n+1} = 1 \cdot F_n + 1 \cdot F_{n-1} + 0 \cdot S_n + 0 \cdot T_n + 0 \cdot n + 0 \cdot 1$
2. $F_n = 1 \cdot F_n + 0 \cdot F_{n-1} + 0 \cdot S_n + 0 \cdot T_n + 0 \cdot n + 0 \cdot 1$
3. $S_{n+1} = S_n + F_{n+1} = 0 \cdot F_n + 0 \cdot F_{n-1} + 1 \cdot S_n + 0 \cdot T_n + 0 \cdot n + 0 \cdot 1 + F_{n+1}$，而 $F_{n+1}$ 已由第一行表示，所以 $S_{n+1} = 1 \cdot F_n + 1 \cdot F_{n-1} + 1 \cdot S_n + 0 \cdot T_n + 0 \cdot n + 0 \cdot 1$
4. $T_{n+1} = T_n + (n+1) F_{n+1} = T_n + n F_{n+1} + F_{n+1}$。将 $F_{n+1}$ 用第一行表示，$n$ 用第五行表示，$1$ 用第六行表示。所以：
   • $T_{n+1} = 0 \cdot F_n + 0 \cdot F_{n-1} + 0 \cdot S_n + 1 \cdot T_n + 0 \cdot n + 0 \cdot 1 + n F_{n+1} + F_{n+1}$
   • 而 $F_{n+1} = 1 \cdot F_n + 1 \cdot F_{n-1}$，所以 $n F_{n+1} = n \cdot F_n + n \cdot F_{n-1}$，其中 $n$ 是第五个分量。
   • 因此，$T_{n+1}$ 的表达式包含 $F_n, F_{n-1}, T_n, n$ 的线性组合，但 $n$ 乘以 $F_n$ 和 $F_{n-1}$ 不是线性组合（因为 $n$ 本身是变量）。实际上，我们需要将 $n F_n$ 视为整体？但状态向量中没有 $n F_n$，所以不能直接线性表示。因此，我们需要增加状态分量，或者换一种思路。

另一种常见方法：注意到 $T(n) = \sum_{i=1}^n i F_i = n S_n - \sum_{i=1}^{n-1} S_i$。因为 $\sum_{i=1}^{n-1} S_i = \sum_{i=1}^{n-1} \sum_{j=1}^i F_j = \sum_{j=1}^{n-1} (n-j) F_j = n \sum_{j=1}^{n-1} F_j - \sum_{j=1}^{n-1} j F_j = n (S_n - F_n) - (T_n - n F_n) = n S_n - n F_n - T_n + n F_n = n S_n - T_n$。整理得：

$$\sum_{i=1}^{n-1} S_i = n S_n - T_n$$

所以

$$T_n = n S_n - \sum_{i=1}^{n-1} S_i$$

这个公式似乎没有简化问题。

更直接的方法：构造 $4 \times 4$ 矩阵，包含 $F_n, F_{n-1}, n F_n, (n-1) F_{n-1}$ 之类的状态。但这样会复杂。

实际上，我们可以定义状态向量为：

$$\mathbf{Y}_n = \begin{bmatrix} F_n \\ F_{n-1} \\ n F_n \\ (n-1) F_{n-1} \\ 1 \end{bmatrix}$$

但递推时 $n$ 会变化。

另一种思路：考虑 $T_n$ 的递推：

$$T_{n} = T_{n-1} + n F_n$$

而 $F_n$ 有递推关系。所以我们需要同时维护 $F_n, F_{n-1}, T_n, n$。但 $n$ 每次加 $1$，可以表示为 $n = (n-1) + 1$，所以 $n$ 可以线性表示。

定义状态向量：

$$\mathbf{Z}_n = \begin{bmatrix} F_n \\ F_{n-1} \\ T_n \\ n \\ 1 \end{bmatrix}$$

则 $\mathbf{Z}_{n+1}$ 为：

1. $F_{n+1} = F_n + F_{n-1}$
2. $F_n = F_n$
3. $T_{n+1} = T_n + (n+1) F_{n+1} = T_n + (n+1)(F_n + F_{n-1}) = T_n + n F_n + n F_{n-1} + F_n + F_{n-1}$
4. $n+1 = n + 1$
5. $1 = 1$

因此，转移矩阵 $A$ 满足 $\mathbf{Z}_{n+1} = A \cdot \mathbf{Z}_n$，其中：

$$A = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

解释：

• 第一行：$F_{n+1} = 1 \cdot F_n + 1 \cdot F_{n-1} + 0 \cdot T_n + 0 \cdot n + 0 \cdot 1$
• 第二行：$F_n = 1 \cdot F_n + 0 \cdot F_{n-1} + 0 \cdot T_n + 0 \cdot n + 0 \cdot 1$
• 第三行：$T_{n+1} = 1 \cdot F_n + 1 \cdot F_{n-1} + 1 \cdot T_n + 1 \cdot n + 0 \cdot 1$（注意还需要 $F_n + F_{n-1}$ 中的 $F_n$ 和 $F_{n-1}$ 系数已包含，但 $n F_n$ 和 $n F_{n-1}$ 中的 $n$ 来自第四列，所以第三行第四列系数为 $1$ 表示 $n$ 的贡献？实际上，$T_{n+1} = T_n + (n+1)(F_n + F_{n-1}) = T_n + n F_n + n F_{n-1} + F_n + F_{n-1}$。所以 $F_n$ 系数为 $1$（来自 $F_n$）和 $n$ 的系数为 $1$（来自 $n F_n$）？但矩阵乘法是线性组合，不能有 $n F_n$ 这样的项，因为 $n$ 和 $F_n$ 是分开的分量。所以我们需要将 $n F_n$ 拆开？实际上，在状态向量中，$n$ 和 $F_n$ 是独立分量，乘积 $n F_n$ 不是分量的线性组合。因此，这个矩阵不能正确表示 $T_{n+1}$。

所以我们需要将 $n F_n$ 也作为状态分量。定义状态向量：

$$\mathbf{W}_n = \begin{bmatrix} F_n \\ F_{n-1} \\ n F_n \\ (n-1) F_{n-1} \\ T_n \\ 1 \end{bmatrix}$$

这样，每个分量都是线性的。递推关系：

1. $F_{n+1} = F_n + F_{n-1}$
2. $F_n = F_n$
3. $(n+1) F_{n+1} = (n+1)(F_n + F_{n-1}) = n F_n + n F_{n-1} + F_n + F_{n-1}$
4. $n F_n = n F_n$（保持不变？实际上，$(n+1) F_{n+1}$ 成为新的第三分量，原来的第三分量 $n F_n$ 在下一状态中变为 $(n+1) F_{n+1}$ 的一部分，但我们需要递推关系）
5. $T_{n+1} = T_n + (n+1) F_{n+1}$
6. $1 = 1$

这样，我们可以写出转移矩阵 $A$。但状态向量有 $6$ 个分量，矩阵为 $6 \times 6$。

具体地，令 $\mathbf{W}_n = [F_n, F_{n-1}, U_n, V_n, T_n, 1]^T$，其中 $U_n = n F_n$，$V_n = (n-1) F_{n-1}$。则 $\mathbf{W}_{n+1}$ 为：

• $F_{n+1} = F_n + F_{n-1}$
• $F_n = F_n$
• $U_{n+1} = (n+1) F_{n+1} = (n+1)(F_n + F_{n-1}) = n F_n + n F_{n-1} + F_n + F_{n-1} = U_n + (V_n + F_{n-1}) + F_n + F_{n-1}$，因为 $V_n = (n-1) F_{n-1}$，所以 $n F_{n-1} = V_n + F_{n-1}$。所以 $U_{n+1} = U_n + V_n + F_n + 2 F_{n-1}$。
• $V_{n+1} = n F_n = U_n$
• $T_{n+1} = T_n + U_{n+1}$（因为 $U_{n+1} = (n+1) F_{n+1}$）
• $1 = 1$

因此，转移矩阵 $A$ 为：

$$A = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 2 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

验证：

• 第一行：$F_{n+1} = 1 F_n + 1 F_{n-1} + 0 U_n + 0 V_n + 0 T_n + 0$
• 第二行：$F_n = 1 F_n + 0 F_{n-1} + 0 U_n + 0 V_n + 0 T_n + 0$
• 第三行：$U_{n+1} = 1 F_n + 2 F_{n-1} + 1 U_n + 1 V_n + 0 T_n + 0$
• 第四行：$V_{n+1} = 1 F_n + 0 F_{n-1} + 1 U_n + 0 V_n + 0 T_n + 0$
• 第五行：$T_{n+1} = 1 F_n + 2 F_{n-1} + 1 U_n + 1 V_n + 1 T_n + 0$
• 第六行：$1 = 0 F_n + 0 F_{n-1} + 0 U_n + 0 V_n + 0 T_n + 1$

初始状态：$n=1$，$\mathbf{W}_1 = [F_1, F_0, U_1, V_1, T_1, 1]^T$。但 Fibonacci 数列通常定义 $F_1=1, F_0=0$。这里 $F_0=0$。$U_1 = 1 \cdot F_1 = 1$，$V_1 = (1-1) F_0 = 0$，$T_1 = 1 \cdot F_1 = 1$。所以 $\mathbf{W}_1 = [1, 0, 1, 0, 1, 1]^T$。

那么 $\mathbf{W}_n = A^{n-1} \cdot \mathbf{W}_1$，$T_n$ 是第五个分量。

因此，算法步骤：

1. 构造 $6 \times 6$ 矩阵 $A$ 和初始向量 $W_1$。
2. 计算 $B = A^{n-1}$（矩阵快速幂）。
3. 计算 $\mathbf{W}_n = B \cdot W_1$。
4. 输出 $\mathbf{W}_n$ 的第五个元素（即 $T_n$）模 $m$。

注意 $n$ 可能为 $1$，此时 $n-1=0$，$A^0$ 是单位矩阵，$\mathbf{W}_1$ 的第五个分量为 $1$，正确。

由于 $n$ 可达 $2^{31}-1$，矩阵快速幂需要 $O(6^3 \log n) = O(216 \log n)$，可以接受。注意取模 $m$，$m$ 也可能很大，但矩阵元素在计算过程中取模即可。