洛谷 P1939 【模板】矩阵加速（数列）——————矩阵快速幂(水题)

骑猪看日落 2022-05-09 10:56 189阅读 0赞

### 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 n<=100 n<=100；

对于60%的数据  n < = 2 ∗ 1 0 7 n<=2\*10^7 n<=2∗107；

对于100%的数据  T < = 100 ， n < = 2 ∗ 1 0 9 T<=100，n<=2\*10^9 T<=100，n<=2∗109；

--------------------

构造矩阵  
 ( 1 0 + 1 1 0 0 0 1 0 ) × ( a 3 a 2 a 1 ) = ( a 4 a 3 a 2 ) \\begin\{pmatrix\}1&0+&1\\\\1&0&0\\\\0&1&0\\end\{pmatrix\}\\times\\begin\{pmatrix\}a\_3\\\\a\_2\\\\a\_1\\end\{pmatrix\} =\\begin\{pmatrix\}a\_4\\\\a\_3\\\\a\_2\\end\{pmatrix\} ⎝⎛1100\+01100⎠⎞×⎝⎛a3a2a1⎠⎞=⎝⎛a4a3a2⎠⎞  
所以，我们这样的话  
 ( 1 0 1 1 0 0 0 1 0 ) n − 2 × ( a 3 a 2 a 1 ) = ( a n a n − 1 a n − 2 ) \\begin\{pmatrix\}1&0&1\\\\1&0&0\\\\0&1&0\\end\{pmatrix\}^\{ n-2\}\\times\\begin\{pmatrix\}a\_3\\\\a\_2\\\\a\_1\\end\{pmatrix\} =\\begin\{pmatrix\}a\_n\\\\a\_\{n-1\}\\\\a\_\{n-2\}\\end\{pmatrix\} ⎝⎛110001100⎠⎞n−2×⎝⎛a3a2a1⎠⎞=⎝⎛anan−1an−2⎠⎞

--------------------

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    const int MAXN = 4;
    const int INF  = 0x3f3f3f3f;
    const int MOD  = 1e9+7;
    
    struct mat{
        ll m[MAXN][MAXN]; } ;
    
    ll N;
    inline mat mul(mat a,mat b)
    {
        
            mat tmp;
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                    {
        
                            tmp.m[i][j]=0;
                            for(int k=1;k<=N;k++)
                                    tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
                    }
            return tmp;
    }
    inline mat pow_mod(mat a,ll n)
    {
        
            mat ans;
            memset(ans.m,0,sizeof(ans.m));
            for(int i=1;i<=N;i++)
                    ans.m[i][i]=1;
    
            while(n)
            {
        
                    if(n&1) ans=mul(ans,a);
                    a=mul(a,a);
                    n>>=1;
            }
            return ans;
    }
    int main()
    {
        
            ll n;
            N=3;
            mat a,b;
            memset(a.m,0,sizeof(a.m));
            memset(b.m,0,sizeof(b.m));
            a.m[1][1]=1;
            a.m[2][1]=1;
            a.m[3][1]=1;
            b.m[1][1]=1;b.m[1][3]=1;
            b.m[2][1]=1;
            b.m[3][2]=1;
            int t;
            scanf("%d",&t);
            while(t--)
            {
        
                    scanf("%lld",&n);
                    if(n<=3)//之前没写这个，TLE了好几次
                    {
        
                            printf("1\n");
                            continue;
                    }
                    mat c=pow_mod(b,n-2);
                    mat d=mul(c,a);
                    printf("%lld\n",d.m[2][1]);
            }
            return 0;
    }