矩阵快速幂=矩阵乘法+快速幂

矩阵乘法

伪代码实现 Mat operator*(Mat a,Mat b) { Mat c; for i:0 --> len for j:0-->len c.mat[i][j] = 0; for k:0-->len c.mat[i][j]=(c.mat[i][j] + (a.mat[i][k]*b.mat[k][j])%MOD)%MOD; return c; } 时间复杂度O(n^3)

实数快速幂

假设你已经有一个函数F(x) = k^x 它可以求 k^1 直到 k^(n-1)
现在的问题是 如何求F(n)？

分治思想

1. 当n是偶数的时候：F(n)=F(n/2)*F(n/2)
2. 当n是奇数的时候：转化成偶数的情况 F(n) = k * F(n - 1)

伪代码实现 /*递归写法*/ int fast_mod(int k, int n, int MOD){ n == 0: return 1; n是奇数： return k * fast_mod(k, n -1, MOD) % MOD; n是偶数： p = fast_mod(k, n >> 1, MOD); return p * p % MOD; } /*非递归写法*/ int quickmod(int a, int b){ ans = 1; 只要b不等于0： 如果b是奇数： ans = (ans*a)%mod; b--； 如果b是偶数： b/=2; a = ((a%mod)*(a%mod))%mod; return ans; } 时间复杂度O（logN）

矩阵快速幂

伪代码实现 Mat fast_mod(Mat A, int n, int MOD){ n == 0: return E; n是奇数： return MulMat(A, fast_mod(A, n - 1), MOD); n是偶数： p = fast_mod(k, n >> 1, MOD); return MulMat(p, p, MOD); } /*对于任何一个矩阵A，定义A^0 = E。E是单位矩阵*/ 朴素矩阵幂运算时间复杂度是O(n^3*m),矩阵快速幂时间复杂度是O(n^3*log m)

例题：Fibonacci

poj-3070

Description

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … An alternative formula for the Fibonacci sequence is.

Given an integer n, your goal is to compute the last 4 digits of Fn.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

原理

F[n]=F[n-1]+F[n-2];
F[0]=0;F[1]=1;F[2]=1;
故而，此题使用矩阵快速幂取模方法

代码

---

/*手残党代码*/ #include #include using namespace std; const int MOD = 10000; int fast_mod(int n) // 求 (t^n)%MOD { int t[2][2] = {1, 1, 1, 0}; //起始矩阵 int ans[2][2] = {1, 0, 0, 1}; // 初始化为单位矩阵 int tmp[2][2]; //自始至终都作为矩阵乘法中的中间变量 while(n) { if(n&1) //n 是奇数，先取出1.实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t { for(int i=0;i<2;++i) for(int j = 0;j<2;++j) tmp[i][j]=ans[i][j]; ans[0][0]=ans[1][1]=ans[0][1]=ans[1][0] = 0; //注意这里要都赋值成 0 for(int i=0;i<2;++i) //ans 乘以一个 起始矩阵 { for(int j=0; j<2;++j) { for(int k=0;k<2;++k) ans[i][j]=(ans[i][j]+(tmp[i][k]*t[k][j])%MOD)%MOD; } } } //下边要实现 t *= t 的操作,同样要先将t赋值给中间变量 tmp ,t清零，之后 t = tmp* tmp for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) tmp[i][j] = t[i][j]; t[0][0] = t[1][1] = 0; t[0][1] = t[1][0] = 0; for(int i = 0; i < 2; ++i) //矩阵乘法 { for(int j = 0; j < 2; ++j) { for(int k = 0; k < 2; ++k) t[i][j]=(t[i][j]+(tmp[i][k]*tmp[k][j])%MOD)%MOD; } } n/=2; } return ans[0][1]; } int main() { int n; while(scanf("%d",&n) && n != -1) { printf("%d ", fast_mod(n)); } return 0; } /*高效代码*/ #include #include using namespace std; const int MOD = 10000; struct matrix { int m[2][2]; }ans, base; matrix multi(matrix a, matrix b) //结构体封装 { matrix tmp; for(int i = 0; i < 2; ++i) { for(int j = 0; j < 2; ++j) { tmp.m[i][j] = 0; for(int k = 0; k < 2; ++k) tmp.m[i][j]=(tmp.m[i][j]+(a.m[i][k]*b.m[k][j])%MOD)%MOD; } } return tmp; } int fast_mod(int n) // 求矩阵 base 的 n 次幂 { base.m[0][0] = base.m[0][1] = base.m[1][0] = 1; base.m[1][1] = 0; ans.m[0][0] = ans.m[1][1] = 1; // ans 初始化为单位矩阵 ans.m[0][1] = ans.m[1][0] = 0; while(n) { if(n & 1) //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t { ans = multi(ans, base); } base = multi(base, base); n >>= 1; } return ans.m[0][1]; } int main() { int n; while(scanf("%d", &n) && n != -1) { printf("%d ", fast_mod(n)); } return 0; }