洛谷P1939 【模板】矩阵加速（数列）

题目描述

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。

输出格式

每行输出一个非负整数表示答案。

输入输出样例

输入 #1

3
6
8
10

输出 #1

4
9
19

说明/提示

对于30%的数据 n<=100；

对于60%的数据 n<=2*10^7；

对于100%的数据 T<=100，n<=2*10^9；

解析：

\(\displaystyle \begin{array}{{>{\displaystyle}l}} \ 现在我需要求的矩阵是:\\ \begin{bmatrix} f[ i]\\ f[ i-1]\\ f[ i-2] \end{bmatrix}\\ 根据题目中给出的条件:f[ x] =f[ x-1] +f[ x-3]\\ 而我们下一步要求出f[ i+1]\\ 所以f[ i+1] =f[ i] +f[ i-2]\\ 所以求初始矩阵为\\ \begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix}\\ 对初始矩阵进行矩阵快速幂然后输出a[ 1][ 1] \end{array}\)

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#define re register
#define Max 200000012
#define int long long
int n;
const int mod=1000000007;
struct Mat {
    int a[4][4];
    Mat() {memset(a,0,sizeof a);}
    inline void build() {
        memset(a,0,sizeof a);
        for(re int i = 1 ; i <= 3 ; ++ i) a[i][i]=1;
    }
};
Mat operator*(Mat &a,Mat &b)
{
    Mat c;
    for(re int k = 1 ; k <= 3 ; ++ k)
        for(re int i = 1 ; i <= 3 ; ++ i)
            for(re int j = 1 ; j <= 3 ; ++ j)
                c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
    return c;
}
Mat ans,a,A;
void quick_Mat(int x)
{
    ans.build();
    while(x) {
        if(x & 1 == 1) ans=ans*a;
        a=a*a;
        x>>=1;
    }
}
signed main()
{
    scanf("%lld",&n);int x;
    A.a[1][1]=1;A.a[2][1]=1;A.a[3][1]=1;
    for(re int i = 1 ; i <= n ; ++ i) {
        scanf("%lld",&x);
        if(x<=3 && x>=1) {
            printf("1\n");
            continue;
        }
        a.a[1][1]=1;a.a[1][2]=0;a.a[1][3]=1;
        a.a[2][1]=1;a.a[2][2]=0;a.a[2][3]=0;
        a.a[3][1]=0;a.a[3][2]=1;a.a[3][3]=0;
        quick_Mat(x-3);
        ans = ans * A;
        printf("%lld\n",ans.a[1][1]);
    }
    return 0;
}