題目鏈接：點擊打開題目
代碼如下：
#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;}新聞熱點
疑難解答
圖片精選
