一道經典的矩陣快速冪模板題。

傳送門1——>快速冪基本思想

傳送門2——>矩陣快速冪講解(教主傳授)

---

代碼(去掉空行43行)

#include<iostream> #include<cstring> using namespace std; int k, m; struct Matrix { //1、構建矩陣快速冪結構體 int a[10][10];Matrix() { memset(a, 0, sizeof(a)); } };//5、構造矩陣運算mul Matrix mul(Matrix A, Matrix B) {Matrix ret;for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++) {for(int k = 0; k < 10; k++)ret.a[i][j] += (A.a[i][k] * B.a[k][j])%m;ret.a[i][j] %= m;} return ret; } //4、構造快速冪pow Matrix pow(Matrix A, int n) {Matrix ret;for(int i=0; i<10; i++) ret.a[i][i]=1; //單位矩陣while(n) {if(n%2 == 1) ret=mul(ret, A);A=mul(A,A);n /= 2;}return ret; } int main() {while(cin>>k>>m) {Matrix B; //2、定義，存儲求出的目標矩陣for(int i=0; i<10; i++) { int x; cin>>x; B.a[i][0]=x; }for(int i=0; i<10; i++) B.a[i][i+1]=1;if(k < 10) { cout << B.a[k][0] << endl; continue; } //3、特判 Matrix ans1=pow(B, k-9); int sum = 0;for(int i=0; i<10; i++) sum += (ans1.a[i][0]*(9-i))%m; //最后乘就可以 cout << sum%m << endl; } return 0; }

---

如果這篇文章對你產生了幫助，就請給博主一個小小的贊吧！大家的點贊是我創作的最大動力！

總結

以上是生活随笔為你收集整理的43行代码AC——HDU 1757 A Simple Math Problem（矩阵快速幂，附快速幂讲解）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。