题目1081：递推数列（矩阵快速幂解递推式）-白红宇

题目1081：递推数列（矩阵快速幂解递推式）

阅读量：6269 次

发布时间：2019-06-22

本文共 1499 字，大约阅读时间需要 4 分钟。

题目1081：递推数列

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：5885

解决：800

题目描述：

给定a0,a1,以及an=p*a(n-1) + q*a(n-2)中的p,q。这里n >= 2。求第k个数对10000的模。

输入：

输入包括5个整数：a0、a1、p、q、k。

输出：

第k个数a(k)对10000的模。

样例输入：

20 1 1 14 5

样例输出：

来源：

1 #include
          
            2 #include
           
             3 #include
            
              4 #include
             
               5 #include
              
                6 #include
               
                 7 #include
                
                  8 #include
                 
                   9 #include
                  10 #include
                   
                    11 12 using namespace std;13 14 typedef long long ll;15 16 const ll mod = 10000;17 18 19 struct Matrix20 {21 ll mat[2][2];22 Matrix()23 {24 memset(mat,0,sizeof(mat));25 }26 Matrix operator *(const Matrix A) const27 {28 Matrix ret;29 for(int i=0;i<2;i++)30 {31 for(int j=0;j<2;j++)32 {33 for(int k=0;k<2;k++)34 ret.mat[i][j] = (ret.mat[i][j]+(mat[i][k]*A.mat[k][j])%mod)%mod;35 }36 }37 return ret;38 }39 };40 41 Matrix quickMul(Matrix x,int k)42 {43 Matrix ret;44 for(int i=0;i<2;i++)45 ret.mat[i][i] = 1;46 while(k>0)47 {48 if(k&1) ret=ret*x;49 k>>=1;50 x=x*x;51 }52 return ret;53 }54 55 int main()56 {57 ll a0,a1,p,q,k;58 while(~scanf("%lld%lld%lld%lld%lld",&a0,&a1,&p,&q,&k))59 {60 Matrix st;61 st.mat[0][0] = p,st.mat[0][1] = q;62 st.mat[1][0] = 1,st.mat[1][1] = 0;63 Matrix a = quickMul(st,k);64 Matrix b;65 b.mat[0][0] = a1;66 b.mat[1][0] = a0;67 a = a*b;68 printf("%lld\n",a.mat[1][0]%mod);69 }70 return 0;71 }