思路与算法

设 $S_i=F_1+\cdots+F_i$。使用列状态 $V_i=(F_i,F_{i-1},S_i)^\mathsf T$，则

$$V_{i+1}=A V_i,\quad A=\begin{pmatrix}1&1&0\\1&0&0\\1&1&1\end{pmatrix}.$$

第三行同时表达 $S_{i+1}=S_i+F_{i+1}=S_i+F_i+F_{i-1}$。初始状态 $V_1=(1,0,1)^\mathsf T$。二进制矩阵幂求 $A^{n-1}$，乘初始向量后取第三项模 $m$。这样直接在固定转移中累加前缀，无须枚举 $n$ 项或依赖除法。

正确性说明

前两维按斐波那契递推更新，第三维在原前缀和上增加新产生的 $F_{i+1}$，所以一次转移同时保持三个状态的含义。初始状态在 $i=1$ 成立，归纳得到 $A^{n-1}V_1=V_n$。快速幂按二进制分解同一个矩阵的幂，单位矩阵处理零指数，最终精确得到此转移。逐项取模保持线性组合的同余类，第三项即前 $n$ 项和的余数。

复杂度

设状态维度为 $d$（本题为固定常数）。初始化转移矩阵和单位矩阵耗时 $O(d^2)$；一次矩阵乘法 $O(d^3)$，二进制幂进行 $O(\log(n+1))$ 轮，最后矩阵乘初始向量 $O(d^2)$。含初始化总时间 $O(d^2+d^3\log(n+1))$，固定维度可简为 $O(\log(n+1))$。矩阵和向量额外空间 $O(d^2)$，不按 $n$ 分配数组。

易错点

1. 第三行应加入新的 $F_{i+1}$，不能只加旧 $F_i$。
2. 初始前缀和为1，指数为 $n-1$。$n=1$、$m=1$ 均须正确。
3. 项值与前缀和是不同输出目标，最终取第三维。
4. 矩阵每累加一个乘积就取模，使用64位；本范围每次模内乘积加模内部分和小于64位上界。
5. 独立答案通过望远镜恒等式 $S_n=F_{n+2}-1$ 和快速倍增求值，另以小规模直接求和验证，不重复参考程序的3维转移。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int D = 3;
ll mod;
struct Matrix {
    ll a[D][D]{};
};
Matrix multiply(const Matrix &x, const Matrix &y) {
    Matrix out;
    for (int i = 0; i < D; i++)
        for (int j = 0; j < D; j++)
            for (int k = 0; k < D; k++)
                out.a[i][j] = (out.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
    return out;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n >> mod;
    ll raw[D][D] = {{1, 1, 0}, {1, 0, 0}, {1, 1, 1}};
    Matrix base, result;
    for (int i = 0; i < D; i++) {
        result.a[i][i] = 1 % mod;
        for (int j = 0; j < D; j++)
            base.a[i][j] = raw[i][j] % mod;
    }
    ll power = n - 1;
    while (power) {
        if (power & 1)
            result = multiply(result, base);
        base = multiply(base, base);
        power >>= 1;
    }
    ll initial[D] = {1, 0, 1}, answer = 0;
    for (int j = 0; j < D; j++)
        answer = (answer + result.a[2][j] * initial[j]) % mod;
    cout << answer << '\n';
}