福州大学算法作业题 - 数列

★实验任务

joyfun 和 joyvan 两兄弟很喜欢数列。 
joyfun 给 joyvan 找来了一个数列{an}。
其中： a1 = x, ai = x * ai-1，(i > 1) joyfun 想考考 joyvan 数列的第 165 位是多少。 
这个问题实在太简单了，joyvan 甚至不需要求助于聪明的你，就知道 a165 = x165。
此外，joyvan 还不屑于计算 x * x * … * x。他表示 x165可以用 x1 * x4 * x32 * x128来更高效地得出。 
由于问题被 joyvan 迅速解决了，joyfun 为了保卫自己的尊严，修改了数列 的通项公式。
新的数列如下： a1 = x, a2 = x * x, ai = u * ai-2 + v * ai-1，(i > 2) joyfun 要求 joyvan 计算出新数列的第 k 位是多少。 
实际上，joyfun 自己也不知道新数列的第 k 位是多少。为了防止被识破，他 求助于聪明的你。
请你计算出数列第 k 位的值，协助 joyfun 保卫他的尊严。

★数据输入

每组数据输入为四个正整数 x，u，v，k，其意义如题面所述。 其中 1 <= x，u，v <= 100。 对 80% 的数据，1 <= k <= 100,000。 对 100% 的数据，1 <= k <= 1000,000,000,000,000,000。 

★数据输出
输出数列的第 k 位。 由于答案可能非常大，请输出答案对 1000,000,007 取模的结果。

解题思路：矩阵快速幂

代码1：

#include<stdio.h>    
#include<stdlib.h>    
#include<math.h>    
#include<string.h>    
#define mod 1000000007;    
  
struct mat {   //matrix    
    __int64 m[2][2];  
};  
  
mat mat_mul(mat &a, mat &b) {  //matrix multiplication:multiply two matrices and return a matrix    
    mat res_mat;  //a matrix store the result    
    memset(res_mat.m, 0, sizeof(res_mat.m));  //allocate memory    
    for (int i = 0; i < 2; ++i)       //2 is order of matrix    
        for (int j = 0; j < 2; ++j)  
            for (int k = 0; k < 2; ++k) {  
                res_mat.m[i][j] += a.m[i][k] * b.m[k][j];  
                res_mat.m[i][j] %= mod;  
            }  
  
    //printf("%d\n", res_mat.m[0][0]);    
    return res_mat;  
}  
  
mat mat_pow(mat &a, __int64 n) {  //get the power matrix of a matrix with order n     
    mat res_mat;  
    memset(res_mat.m, 0, sizeof(res_mat.m));  
    for (int i = 0; i < 2; ++i)  
        res_mat.m[i][i] = 1;  
    while (n) {  
        if (n & 1)  
            res_mat = mat_mul(res_mat, a);  
        a = mat_mul(a, a);  
        n >>= 1;  
    }  
    return res_mat;  
}  
  
int main() {  
    int x, u, v;  
    __int64 k;  
    scanf("%d %d %d %i64d", &x, &u, &v, &k);  
    //matrix a    
    mat a, b;  
    a.m[0][0] = v;  
    a.m[0][1] = u;  
    a.m[1][0] = 1;  
    a.m[1][1] = 0;  
    b.m[0][0] = x * x;  
    b.m[0][1] = 0;  
    b.m[1][0] = x;  
    b.m[1][1] = 0;  
  
    if (k == 1)  
        printf("%d\n", x);  
    else if (k == 2)  
        printf("%d\n", x*x);  
    else {  
        mat res = mat_pow(a, k - 2);  
        //printf("%d %d\n", res.m[0][0], res.m[1][0]);    
        res = mat_mul(res, b);  
        printf("%i64d\n", res.m[0][0]);  
    }  
    return 0;  
}  

代码2：

#include<stdio.h>    
#define chu 1000000007    
struct juzhen//定义一个二维数组     
{    
    __int64 a[2][2];    
};    
  
//矩阵相乘   
juzhen juzhen_x(juzhen x,juzhen y)    
{    
    juzhen result;    
    result.a[0][0]=(x.a[0][0]*y.a[0][0]%chu+x.a[0][1]*y.a[1][0]%chu)%chu;    
    result.a[0][1]=(x.a[0][0]*y.a[0][1]%chu+x.a[0][1]*y.a[1][1]%chu)%chu;    
    result.a[1][0]=(x.a[1][0]*y.a[0][0]%chu+x.a[1][1]*y.a[1][0]%chu)%chu;    
    result.a[1][1]=(x.a[1][0]*y.a[0][1]%chu+x.a[1][1]*y.a[1][1]%chu)%chu;    
    return result;    
}    
    
//快速幂算法     
juzhen fast_mi(juzhen  x,__int64 n)    
{    
    juzhen res = {{1,0,0,1}};//单位矩阵     
    while(n)    
    {    
        if(n&1)    
            res=juzhen_x(res,x);    
        x=juzhen_x(x,x);    
        n>>=1;    
    }    
    return res;    
}    
    
int main()    
{    
    __int64 x, u, v, k,result;    
    scanf("%i64d %i64d %i64d %i64d",&x,&u,&v,&k);    
    juzhen a ={{v,u,1,0}};//要乘的矩阵     
    juzhen k1=fast_mi(a,k-2);    
    result= ((k1.a[0][0]*x*x)%chu+(k1.a[0][1]*x)%chu)%chu;          
    printf("%i64d",result);    
}    

代码3：

#include<iostream>  
#include<string.h>  
using namespace std;  
const long  mod=1000000007;  
struct mat  
{       
    __int64  t[2][2];//二维数组  
    //定义结构体矩阵  
};  
//定义矩阵的乘法的函数  
mat multi(mat x,mat y)  
{     
    mat ans;    
    memset(ans.t,0,sizeof(ans.t));    
    for(int i=0;i<2;i++)   
    {      
        for(int j=0;j<2;j++)     
        {         
            for(int k=0;k<2;k++)      
            {           
                ans.t[i][j]+=x.t[i][k]*y.t[k][j];  
                ans.t[i][j]%=mod; //取余运算，防止越界   
            }    
        }    
    }   
    return ans;  
}  
//快速幂求解就是利用二进制来进行分解  
mat pow(mat a,__int64 n)  
{   
    mat ans;    
    //构造一个ans的单位矩阵  
    for(int i=0;i<2;i++)  
    {       
        for(int j=0;j<2;j++)   
        {         
            if(i==j)ans.t[i][j]=1;  
            else ans.t[i][j]=0;    
        }  
    }  
    //利用分治的方法  例如8=4*2  4=2*2  
    while(n>0)     
    {       
        if(n%2==1)    
        {            
            ans=multi(ans,a); //进行乘法运算   
        }         
        a=multi(a,a); //进行乘法运算  
        n/=2;     
    }     
    return ans;  
}   
int main()  
{     
  
    __int64 x,a0,a1,u,v;  
    __int64 k;  
    scanf("%i64d %i64d %i64d %i64d",&x,&u,&v,&k);  
    a0=x;  
    a1=x*x;  
          
        k--;  
        if(k==1)printf("%i64d",a1);   //if判断  
        else if(k==0)printf("%i64d",a0);  
        else     
        {      
            //【0】【0】就是第一行第一列,【0】【1】第一行第二列  
            mat m;        
            m.t[0][0]=v;      
            m.t[0][1]=u;           
            m.t[1][0]=1;         
            m.t[1][1]=0;        
            //快速幂求解  
            m=pow(m,k-1);         
            printf("%i64d",((a1*m.t[0][0])%mod+(a0*m.t[0][1])%mod)%mod);  
               
        }      
      
    return 0;  
}