欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-03 18:36:18
★实验任务 ★数据输入 ★数据输出 输出数列的第 k 位。 由于答案可能非常大,请输出答案对 1000,000,007 取模的结果。 代码1: 代码2: 代码3: ......

★实验任务

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;  
}