POJ-3070 Fibonacci 快速矩阵幂

简单的快速矩阵幂：

Fn　　　 1    1              Fn-1
　　 =                 *   
Fn-1　　 1    0　　　　  Fn-2

把前面的矩阵作快速幂就可以了。

代码如下：

#include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #define MOD 10000 using namespace std;struct Matrix // ['meitriks] {int a[2][2];void New (int x, int y, int z, int w){a[0][0] = x, a[0][1] = y;a[1][0] = z, a[1][1] = w;}Matrix operator * (Matrix p) {int sum = 0;Matrix ret;for (int i = 0; i < 2; ++i) {for (int k = 0; k < 2; ++k) {sum = 0;for (int j = 0; j < 2; ++j) {sum += a[i][j] * p.a[j][k];}ret.a[i][k] = sum % MOD;}}return ret;}Matrix _pow(Matrix p, int b) {Matrix ret;ret.New(1, 0, 0, 1);while (b) {if (b & 1) {ret = ret * p;}p = p * p;b >>= 1;}return ret; }void print(){for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {printf("%d ", a[i][j]);}puts("");}} }M, P, ans;int main() {int N;P.New(1, 1, 1, 0);M.New(1, 0, 0, 0); // 保存这F0和F1while (scanf("%d", &N), N != -1) {ans = ans._pow(P, N); ans = ans * M;printf("%d\n", ans.a[1][0]);}return 0; }

总结

以上是生活随笔为你收集整理的POJ-3070 Fibonacci 快速矩阵幂的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。