【模板】矩阵乘法优化线性递推

佚名 6年前 (2019-05-06) 随笔 1669人围观抢沙发百度已收录

代码如下

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long LL;

int n;

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

void solve(){
    int ans[3]={1,1,1};
    int id[3][3]={{1,0,0},{0,1,0},{0,0,1}};
    int S[3][3]={{1,0,1},{1,0,0},{0,1,0}};
    n-=3;
    for(;n;n>>=1,mulself(S,S))if(n&1)mulself(id,S);
    mul(id,ans);
    printf("%d\n",ans[0]);
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(n<=3)puts("1");
        else solve();
    }
    return 0;
}