福州大学算法作业题 - 数列
2018-10-29 15:26:18来源:博客园 阅读 ()
★实验任务
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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:福州大学算法作业题 - 最长子串
下一篇:福州大学算法作业题 - 加法运算
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash