杭电 oj Array Challenge(矩阵快速幂+找规律）

墨蓝 2022-05-16 11:51 181阅读 0赞

题目链接：[这里写链接内容][Link 1]  
先求出式子的前几项  
然后这个式子和h的式子是非常像的  
![这里写图片描述][70]

得到递推式后就可以用矩阵快速幂了  
详细看代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<map>
    #include<vector>
    #include<queue>
    #include<set>
    #include<iomanip>
    #include<cctype>
    using namespace std;
    #define ll long long
    #define edl putchar('\n')
    #define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define FOR(i,a,b) for(int i=a;i<=b;i++)
    #define ROF(i,a,b) for(int i=a;i>=b;i--)
    #define FORLL(i,a,b) for(ll i=a;i<=b;i++)
    #define ROFLL(i,a,b) for(ll i=a;i>=b;i--)
    #define mst(a) memset(a,0,ssizeof(a))
    #define mstn(a,n) memset(a,n,ssizeof(a))
    #define zero(x)(((x)>0?(x):-(x))<eps)
    const int ssize=3;
    const int mod=1000000007;
    struct Matrix {
        ll a[ssize][ssize];
        Matrix() {
            memset(a,0,sizeof(a));
        }
        void init() {
            for(int i=0; i<ssize; i++)
                for(int j=0; j<ssize; j++)
                    a[i][j]=(i==j);
        }
        Matrix operator + (const Matrix &B)const {
            Matrix C;
            for(int i=0; i<ssize; i++)
                for(int j=0; j<ssize; j++)
                    C.a[i][j]=(a[i][j]+B.a[i][j])%mod;
            return C;
        }
        Matrix operator * (const Matrix &B)const {
            Matrix C;
            for(int i=0; i<ssize; i++)
                for(int k=0; k<ssize; k++)
                    for(int j=0; j<ssize; j++)
                        C.a[i][j]=(C.a[i][j]%mod+1LL*a[i][k]*B.a[k][j]%mod+mod)%mod;
            return C;
        }
        Matrix operator ^ (const ll &t)const {
            Matrix A=(*this),res;
            res.init();
            ll p=t;
            while(p) {
                if(p&1)res=res*A;
                A=A*A;
                p>>=1;
            }
            return res;
        }
    };
    
    int main() {
    
        int t;
        scanf("%d",&t);
        Matrix a,b;
        Matrix ans;
        a.a[0][0]=4,a.a[0][1]=17,a.a[0][2]=-12;
        a.a[1][0]=1,a.a[1][1]=0,a.a[1][2]=0;
        a.a[2][0]=0,a.a[2][1]=1,a.a[2][2]=0;
        b.a[0][0]=1255,b.a[1][0]=197,b.a[2][0]=31;
        while(t--){
            ll n;
            scanf("%lld",&n);
            if (n == 2)
            {
                printf("31\n");
                continue;
            }
            else if (n == 3)
            {
                printf("197\n");
                continue;
            }
            else if (n == 4)
            {
                printf("1255\n");
                continue;
            }
            else{
                ans=a^(n-4);
                ll res=(ans.a[0][0]*1255%mod+ans.a[0][1]*197%mod+ans.a[0][2]*31%mod+mod)%mod;
                printf("%lld\n",res);
            }
        }   
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6172
[70]: /images/20220516/85e4d209f2444fda8ee7700d46f162a2.png