@zzzc18 2017-11-09T03:49:02.000000Z 字数 900 阅读 811

# 矩阵快速幂

模板库

$F_n=F_{n-1}+F_{n-3}$

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;LL n;const LL MOD = 1e9+7;struct Matrix{    LL mat[5][5];    Matrix(){        memset(mat,0,sizeof(mat));    }}BASE,A;Matrix operator * (const Matrix &X,const Matrix &Y){    Matrix re;    for(int i=1;i<=3;i++){        for(int j=1;j<=3;j++){            for(int k=1;k<=3;k++){                re.mat[i][j]+=X.mat[i][k]*Y.mat[k][j]%MOD;                re.mat[i][j]%=MOD;            }        }    }    return re;}void DEBUG(Matrix P){    for(int i=1;i<=3;i++){        for(int j=1;j<=3;j++){            printf("%d ",P.mat[i][j]);        }        puts("");    }}Matrix qpow(const Matrix &x,LL k){    Matrix mul=x;    Matrix re;    re.mat[1][1]=re.mat[2][2]=re.mat[3][3]=1;    for(LL i=1;i<=k;i<<=1){        if(i&k)            re=mul*re;        mul=mul*mul;    }    return re;}int main(){    BASE.mat[1][1]=1;    BASE.mat[1][3]=1;    BASE.mat[2][1]=1;    BASE.mat[3][2]=1;    A.mat[1][1]=A.mat[2][1]=A.mat[3][1]=1;    int kase;    scanf("%d",&kase);    while(kase--){        scanf("%lld",&n);        if(n<=3)            puts("1");        else            printf("%lld\n",(qpow(BASE,n-3)*A).mat[1][1]);    }    return 0;}

• 私有
• 公开
• 删除