ACdream 1060 递推数（矩阵快速幂+找循环节）

桃扇骨 2022-06-12 03:26 109阅读 0赞

题目链接：  
[ACdream 1060][]

题意：  
已知A(0)=0,A(1)=1,A(n)=3∗A(n−1)\+A(n−2)(n≥2) .  
求 A(A(A(A(N))))Mod(1e9\+7) .

题解：  
这种题一看就是用矩阵乘法来做啊。  
因为A(n)=3∗A(n−1)\+A(n−2) 。  
那么我们容易构造得到矩阵M ：

M=\[31 10 \]

显然，  (A(n),A(n−1))=(A(n−1),A(n−2))∗M.   
如果我们先算  A(A(A(A(N))))  再模一定会爆  longlong  。  
所以找一下循环节就可以了。

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1060
    * Verdict: Accepted
    * Submission Date: 2017-07-12 19:55:32
    * Time: 236MS
    * Memory: 1664KB
    */
    #include<bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    int mod;
    struct matrix
    {
        ll a[2][2];
        void init()
        {
            for(int i=0;i<2;i++){
                for(int j=0;j<2;j++)
                {
                    a[i][j] = (i==j);
                }
            }
        }
    };
    matrix multi(matrix a,matrix b)
    {
        matrix c;
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                c.a[i][j] = 0;
                for(int k=0;k<2;k++){
                    c.a[i][j] += (a.a[i][k]*b.a[k][j]);
                    c.a[i][j]%=mod;
                }
            }
        }
        return c;
    }
    matrix mul(matrix s,ll k)
    {
        matrix ans;
        ans.init();
        while(k>=1)
        {
            if(k&1){
                ans = multi(ans,s);
            }
            k>>=1;
            s = multi(s,s);
        }
        return ans;
    }
    int main()
    {
        int t;
        ll n;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld",&n);
            matrix s,e;
            s.a[0][0] = 3; s.a[0][1] = 1;
            s.a[1][0] = 1; s.a[1][1] = 0;
            mod = 240;//循环节
            if(n>=2)
            {
                e = mul(s,n-1);
                n = e.a[0][0];
            }
            mod = 183120;//循环节
            if(n>=2)
            {
                e = mul(s,n-1);
                n = e.a[0][0];
            }
            mod = 222222224;//循环节
            if(n>=2)
            {
                e = mul(s,n-1);
                n = e.a[0][0];
            }
            mod = 1000000007;
            if(n>=2)
            {
                e= mul(s,n-1);
                n = e.a[0][0];
            }
            printf("%lld\n",n);
        }    
        return 0;
     }

[ACdream 1060]: http://acdream.info/problem?pid=1060