51Nod 1126 求递推序列的第N项——————矩阵快速幂

╰+哭是因爲堅強的太久メ 2022-05-09 10:34 136阅读 0赞

# 1126 求递推序列的第N项 #

基准时间限制：1 秒  
空间限制：131072 KB  
分值: 10  
难度：2级算法题

有一个序列是这样定义的： f ( 1 ) = 1 , f ( 2 ) = 1 , f ( n ) = ( A ∗ f ( n − 1 ) + B ∗ f ( n − 2 ) ) &ThickSpace; m o d &ThickSpace; 7. f(1) = 1, f(2) = 1, f(n) = (A \* f(n - 1) + B \* f(n - 2)) \\;mod\\; 7. f(1)=1,f(2)=1,f(n)=(A∗f(n−1)\+B∗f(n−2))mod7.  
给出A，B和N，求 &ThickSpace; f ( n ) &ThickSpace; \\;f(n)\\; f(n)的值。

#### Input ####

输入3个数： A , B , N A,B,N A,B,N。数字之间用空格分割。 ( − 10000 < = A , B < = 10000 , 1 < = N < = 1 0 9 ) (-10000 <= A, B <= 10000, 1 <= N <= 10^9) (−10000<=A,B<=10000,1<=N<=109)

#### Output ####

输出f(n)的值。

#### Input示例 ####

3 -1 5

#### Output示例 ####

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

我们知道：  
 f ( 1 ) = 1 f ( 2 ) = 1 f ( n ) = ( A ∗ f ( n − 1 ) + B ∗ f ( n − 2 ) ) f(1) = 1\\\\ f(2) = 1\\\\ f(n) = (A \* f(n - 1) + B \* f(n - 2)) f(1)=1f(2)=1f(n)=(A∗f(n−1)\+B∗f(n−2))  
可以构造矩阵：  
 ( A B 1 0 ) × ( f n − 1 f n − 2 ) = ( f n f n − 1 ) \\large \\begin\{pmatrix\}A & B\\\\ 1 & 0\\end\{pmatrix\}\\times\\begin\{pmatrix\}f\_\{n-1\}\\\\f\_\{n-2\}\\end\{pmatrix\}=\\begin\{pmatrix\}f\_\{n\}\\\\f\_\{n-1\}\\end\{pmatrix\} (A1B0)×(fn−1fn−2)=(fnfn−1)

因为：  
 ( A B 1 0 ) × ( f 2 f 1 ) = ( f 3 f 2 ) \\large \\begin\{pmatrix\}A & B\\\\ 1 & 0\\end\{pmatrix\}\\times\\begin\{pmatrix\}f\_\{2\}\\\\f\_\{1\}\\end\{pmatrix\}=\\begin\{pmatrix\}f\_3\\\\f\_2\\end\{pmatrix\} (A1B0)×(f2f1)=(f3f2)  
所以  
 ( A B 1 0 ) n − 1 × ( f 1 f 2 ) = ( f n f n − 1 ) \\large \\begin\{pmatrix\}A & B\\\\ 1 & 0\\end\{pmatrix\}^\{n-1\}\\times\\begin\{pmatrix\}f\_\{1\}\\\\f\_\{2\}\\end\{pmatrix\}=\\begin\{pmatrix\}f\_\{n\}\\\\f\_\{n-1\}\\end\{pmatrix\} (A1B0)n−1×(f1f2)=(fnfn−1)

/*
    
            f[1]=1;
            f[2]=1;
            f[n]=A*f[n-1]+B*f[n-2];
    
            A,B,n
            f[n]%7;
    
    */
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    const int INF = 0x3f3f3f3f;
    const int MAXN = 11;
    const int MOD = 7;
    
    ll N;
    ll b_n=0;
    ll C[MAXN];
    ll h[MAXN];
    
    struct mat{
        ll m[MAXN][MAXN];};
    
    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;
    }
    mat pow_mod(mat a,ll n)
    {
        
            mat ans;
            for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            ans.m[i][j]=(i==j);
            while(n)
            {
        
                    if(n&1) ans=mul(ans,a);
                    a=mul(a,a);
                    n>>=1;
            }
            return ans;
    }
    void init(mat &res,mat &H)
    {
        
            for(int i=1;i<=N;i++)
                    res.m[1][i]=C[i];
            res.m[1][N]=b_n;
    
            for(int i=2;i<=N;i++)
                    for(int j=1;j<=N;j++)
                            res.m[i][j]=(i==j+1);
            res.m[N][N-1]=0;
            res.m[N][N]=1;
            for(int i=1;i<=N;i++)
            {
        
                    H.m[i][1]=h[N-i];
                    for(int j=2;j<=N;j++)
                            H.m[i][j]=0;
            }
            H.m[N][1]=1;
    }
    void slove(ll k,ll n)
    {
        
            mat res,H;
            init(res,H);
            res=pow_mod(res,n-k+1);
            res = mul(res,H);
            ll ans=res.m[1][1];
    
            printf("%lld\n",ans%MOD);
    }
    
    int main()
    {
        
            h[1]=1;
            h[2]=1;
            ll k=2;
            ll n,A,B;
            while(~scanf("%lld %lld %lld",&A,&B,&n))
            {
        
                    C[1]=A;
                    C[2]=B;
                    N=k+1;
                    slove(k,n-1);
            }
            return 0;
    }