矩阵快速幂

先推出\(T_n\)与\(F_n\)的关系，再用矩阵快速幂求

\(S_i=F_{i+2}-1\)

\(T_n=(F_1+2\times F_2+3\times F_3\dots+n\times F_n)\pmod m\)

\(\;\;\;\;\; =((F_1+F_2+F_3\dots+F_n)+(F_2+F_3\dots+F_n)+(F_3\dots+F_n)\dots+F_n)\pmod m\)

\(\;\;\;\;\; =(S_n+(S_n-F_1)+(S_n-F_1-F_2)\dots+(S_n-F_1-F_2\dots-F_{n-1}))\pmod m\)

\(\;\;\;\;\; =(n\times S_n-(S_1+S_2+S_3\dots+S_{n-1}))\pmod m\)

\(\;\;\;\;\; =(n\times S_n-(F_3-1+F_4-1+F_5-1\dots+F_{n+1}-1))\pmod m\)

\(\;\;\;\;\; =(n\times S_n-(F_3+F_4+F_5\dots+F_{n+1}-(n+1-3+1)))\pmod m\)

\(\;\;\;\;\; =(n\times S_n-(F_3+F_4+F_5\dots+F_{n+1}-(n+1-3+1)))\pmod m\)

\(\;\;\;\;\; =(n\times S_n-(F_3+F_4+F_5\dots+F_{n+1})+n-1)\pmod m\)

\(\;\;\;\;\; =(n\times S_n-(F_1+F_2+F_3\dots+F_{n+1})+n-1+F_1+F_2)\pmod m\)

\(\;\;\;\;\; =(n\times S_n-S_{n+1}+n-1)\pmod m\)

\(\;\;\;\;\; =(n\times F_{n+2}-1-n-F_{n+3})+1+n+1)\pmod m\)

\(\;\;\;\;\; =(n\times F_{n+2}-F_{n+3}+2)\pmod m\)

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,mod=1e4;
struct mac{
    long long m[5][5];
    mac operator*(mac &b){
        mac c;
        for(long long i=1;i<=2;i++){
            for(long long j=1;j<=2;j++){
                c.m[i][j]=0;
                for(long long k=1;k<=2;k++)c.m[i][j]=((c.m[i][j]+m[i][k]*b.m[k][j]%mod)%mod+mod)%mod;
            }
        }
        return c;
    }
}base;
mac pow(mac a,long long b){
    mac r=a;
    while(b){
        if(b%2)r=r*a;
        b/=2;
        a=a*a;
    }
    return r;
}
void bcle(){
    base.m[1][1]=base.m[1][2]=base.m[2][1]=1;
    base.m[2][2]=0;
}
int main(){
    scanf("%lld%lld",&n,&mod);
    if(mod==1)printf("0");
    else if(n<=2)printf("1");
    else{
        int x,y;
        bcle();
        x=n*pow(base,n+1).m[1][2]%mod;
        bcle();
        y=pow(base,n+2).m[1][2]%mod;
        printf("%lld",(x-y+2+mod)%mod);
    }
}

LOJP10222「一本通 6.5 例 4」佳佳的 Fibonacci

原文：https://www.cnblogs.com/gzezzry/p/12236515.html