首页 > 其他 > 详细

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

时间:2020-01-27 18:22:44      阅读:49      评论:0      收藏:0      [点我收藏+]

标签:clas   while   pan   include   mac   mat   

矩阵快速幂

先推出\(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

标签:clas   while   pan   include   mac   mat   

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

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号