题面

<center>矩阵加速<center>
<center>时间限制1.00s  内存限制125.00MB<center>

题目描述
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a数列的第n项对1000000007(10^9+7)取余的值。

输入格式
第一行一个整数T,表示询问个数。

以下T行,每行一个正整数n。

输出格式
每行输出一个非负整数表示答案。
样例输入

3
6

8
10

样例输出

4

9
19

思路

核心算法为:矩阵快速幂
核心思路为:构造矩阵等式(初始矩阵),然后f[n]的求解既可以转化为:初始矩阵的几次幂*初项。
**a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)**
由这两个条件,可构造:
在这里插入图片描述在这里插入图片描述

源码

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define maxn 5
#define mo 1000000007
using namespace std;
int n=3;
struct ahaha{
    ll a[maxn][maxn];     //一定要用long long存矩阵,否则在过程中会爆掉
    ahaha(){
        memset(a,0,sizeof a);
    }
    inline void build(){     //建造单位矩阵
        for(int i=1;i<=n;++i)a[i][i]=1;
    }
}a;
inline ahaha operator *(const ahaha &x,const ahaha &y){     //重载运算符
    ahaha z;
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mo)%mo;
    return z;
}
ll k;
inline ahaha  fun(ahaha a,ll n){//a的n次幂
    ahaha ans;
    ans.build();
    while(n){
        if(n&1) ans=ans*a;
        n>>=1;
        a=a*a;
    }
    return ans;
}
int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
    int T;
    ll b;
    cin>>T;
    ahaha t;
    t.a[1][1]=1;t.a[1][2]=0;t.a[1][3]=1;
    t.a[2][1]=1;t.a[2][2]=0;t.a[2][3]=0;
    t.a[3][1]=0;t.a[3][2]=1;t.a[3][3]=0;
   ll sum=0;b=0;
    while(T--){
            sum=0;
            cin>>b;
            //b++;cout<<b<<":";
            if(b<4) {
                cout<<"1\n";continue;
            }
            ahaha ans;
            ans=fun(t,b-3);
            sum+=ans.a[1][1];
            sum+=ans.a[1][2];
            sum+=ans.a[1][3];
            sum%=mo;
            cout<<sum<<"\n";
    }
    return 0;
}
Last modification:November 13th, 2019 at 07:14 pm
如果觉得我的文章对你有用,请随意赞赏