福州大学算法作业题 - 数列
程序员文章站
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; }
下一篇: 河南自驾游免费的景点