莫欺少年穷，修魔之旅在这开始—>算法提高课题解

推导：

$T_n=f_1+2f_2+3f_3+…+nf_n$

$P_n=n\cdot S_n-T_n=(n-1)f_1+(n-2)f_2+..+f_{n-1}$

$P_{n+1}=(n+1)\cdot S_{n+1}-T_{n+1}=nf_1+(n-1)f_2+..+2f_{n-1}+f_n$

$P_{n+1}-P_n=S_n$

总结：

$f_n=f_{n-1}+f_{n-2}$

$S_n=S_{n-1}+f_n$

$P_n=P_{n-1}+S_{n-1}$

$T_n=n\cdot S_n-P_n$

思路：

$设\ F_n=\begin{bmatrix}f_n&f_{n+1}&S_n&P_n\end{bmatrix}$

$\begin{aligned}F_n\cdot A& = F_{n+1}\\\\A&=\begin{bmatrix}0&1&0&0\\\\ 1&1&1&0\\\\ 0&0&1&1\\\\0&0&0&1 \end{bmatrix} \end{aligned}$

$F_n=F_1\cdot A^{n-1}$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int n,m;

void mul(int c[][4],int a[][4],int b[][4])
{
    int temp[4][4]={0};
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                temp[i][j]=(temp[i][j]+(LL)a[i][k]*b[k][j])%m;
    memcpy(c,temp,sizeof temp);
}

int main()
{
    cin>>n>>m;

    int f[4][4]={1,1,1,0};
    int a[4][4]={
        {0,1,0,0},
        {1,1,1,0},
        {0,0,1,1},
        {0,0,0,1}
    };

    int k=n-1;
    while(k) //矩阵快速幂
    {
        if(k&1) mul(f,f,a);
        mul(a,a,a);
        k>>=1;
    }

    cout<<(((LL)n*f[0][2]-f[0][3])%m+m)%m<<endl;

    return 0;
}