题面

给定\(n,m\)，求：

\[ T(n)=\sum_{i=1}^ni\times f_i \]

其中\(f_i\)为斐波那契数列的第\(i\)项

题解

不妨设：

\[ S(n)=\sum_{i=1}^nf_i \]

则可以设：

\[ P(n)=nS(n)-T(n)=\sum_{i=1}^{n-1}(n-i)\times f_i \]

所以有：

\[ P(n+1)=\sum_{i=1}^{n}(n+1-i)\times f_i=\sum_{i=1}^n(n-i)\times f_i+\sum_{i=1}^nf_i\\ =\sum_{i=1}^{n-1}(n-i)\times f_i+0\times f_n+S(n)=P(n)+S(n) \]

然后就可以用矩阵乘法加速递推了。

#include 
    
     #include 
     
      int n, m;struct Matrix {    int a[4][4];    Matrix() { memset(a, 0, sizeof a); }    inline int* operator [] (const int &x) { return a[x]; }    inline Matrix operator * (Matrix &b) const {        Matrix ret;        for(int i = 0; i < 4; ++i)            for(int k = 0; k < 4; ++k)                for(int j = 0; j < 4; ++j)                    (ret[i][j] += 1ll * a[i][k] * b[k][j] % m) %= m;        return ret;    }} S, T;int main () {    scanf("%d%d", &n, &m); int k = n;    S[0][1] = 1;    T[0][0] = T[0][1] = T[0][2] = 1;    T[1][0] = T[1][2] = 1;    T[2][2] = T[2][3] = 1;    T[3][3] = 1;    while(k) {        if(k & 1) S = S * T;        T = T * T, k >>= 1;    }    printf("%lld\n", (1ll * n * S[0][2] % m + m - S[0][3]) % m);    return 0;}