【51Nod】1126 - 求递推数列的第N项（矩阵快速幂 & C++运算符重载）

2019-11-06 07:41:43

字体：大中小

来源：转载

供稿：网友

题目链接：点击打开题目

这里写图片描述

代码如下：

#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <stack>#include <vector>#include <algorithm>using namespace std;#define INF 0x3f3f3f3f#define CLR(a,b) memset(a,b,sizeof(a))#define PI acos(-1.0)#define LL long longconst int MOD = 7;struct Matrix{ int h,w; int m[3][3]; void init(int op) { if (op == 0) //初始化矩阵 CLR(this->m,0); else if (op == 1) //初始化为单位矩阵 { this->h = this->w = 2; CLR(this->m,0); this->m[1][1] = this->m[2][2] = 1; } else if (op == 2) //初始化为初始矩阵 { this->h = 1; this->w = 2; CLR(this->m,0); this->m[1][1] = this->m[1][2] = 1; } } void init(int A,int B) { this->w = this->h = 2; CLR(this->m,0); this->m[1][1] = A; this->m[2][1] = B; this->m[1][2] = 1; } Matrix Operator * (Matrix a) { Matrix t; t.h = this->h; t.w = a.w; t.init(0); for (int i = 1 ; i <= this->h ; i++) { for (int j = 1 ; j <= a.w ; j++) { if (this->m[i][j]) for (int k = 1 ; k <= this->w ; k++) { t.m[i][k] = (t.m[i][k] + this->m[i][j] * a.m[j][k] % MOD) % MOD; } } } return t; } Matrix quickMod(int n) { Matrix t; t.init(1); while (n) { if (n & 1) t = t * (*this); *this = (*this) * (*this); n >>= 1; } return t; }};int main(){ int A,B,n; scanf ("%d %d %d",&A,&B,&n); if (n == 1 || n == 2) puts("1"); else { Matrix PR,ans,ori; pr.init(2); ori.init(A,B); ori = ori.quickMod(n-2); ans = pr * ori; printf ("%d/n",(ans.m[1][1] % MOD + MOD) % MOD); } return 0;}

上一篇：c#调用c++写成的dll文件,返回char*，返回数组，用ref接收，byte[] (zz)

下一篇：C++实验2-分段函数求值