思路与算法

要让含下标 $i$ 的加权和也使用固定转移，令

$$V_i=(iF_i,\ iF_{i-1},\ F_i,\ F_{i-1},\ T_i)^\mathsf T.$$

由 $F_{i+1}=F_i+F_{i-1}$ 可得固定矩阵

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

第一行是 $(i+1)F_{i+1}=iF_i+iF_{i-1}+F_i+F_{i-1}$；第二行是 $(i+1)F_i=iF_i+F_i$；最后一行在旧 $T_i$ 上增加第一行产生的新加权项。初始状态为 $V_1=(1,0,1,0,1)^\mathsf T$。对该5阶矩阵求 $n-1$ 次幂并作用到初始向量，取第五项。

正确性说明

逐行等式分别更新下一项的两个加权斐波那契数、两个普通斐波那契数和加权前缀和。每一行只含旧状态的固定线性组合，因此该矩阵确实独立于 $i$。初始向量给出 $F_1=1,F_0=0,T_1=1$，归纳每次转移后五维含义均成立。二进制快速幂等价于连续应用 $n-1$ 次同一转移，并在 $n=1$ 时返回单位矩阵。所有运算只涉及加乘，逐次取模不影响最终余数，故第五项为所求 $T_n\bmod m$。

复杂度

设状态维度为 $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,F_{i-1},T_i$ 无法用固定系数表达下标变化，还需两维加权状态。
2. 新加权项是 $(i+1)F_{i+1}$，最后一行不能误用旧 $iF_i$。
3. $n,m$ 可达 $2^{31}-1$，指数和变量用64位。模内乘积最大约 $4.62\times10^{18}$，再加一个模内部分和仍在64位内；必须每累加一个乘积就取模，不能先累加5个原始乘积。
4. $n=1$ 的零指数、模数1和最大系数均覆盖。单位矩阵也要对模数规范化。
5. 独立答案使用 $T_n=nF_{n+2}-F_{n+3}+2$ 与快速倍增；此恒等式可由求和递推验证，并已与800个小范围逐项加权和交叉核对。训练数据非官方原版。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int D = 5;
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, 1, 1, 0}, {1, 0, 1, 0, 0}, {0, 0, 1, 1, 0}, {0, 0, 1, 0, 0}, {1, 1, 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, 0, 1}, answer = 0;
    for (int j = 0; j < D; j++)
        answer = (answer + result.a[4][j] * initial[j]) % mod;
    cout << answer << '\n';
}