[poj 3070] Fibonacci

先前就知道Fibonacci数列递推公式的矩阵形式，但是只会用数学归纳法证，不知道怎么构造。

今天生物课上突然有了灵感……既然已经学习了矩阵乘法的线性组合意义——

$$\begin{bmatrix}F_i & F_{i+1}\end{bmatrix}\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}=\begin{bmatrix}F_{i+1} & F_{i+2}\end{bmatrix}$$

想测试一下，便找到了poj 3070。很高兴我的式子和题目中的不同~

隐约感受到了矩阵乘法的威力……

然后中午写了个矩阵快速幂。

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2, MASK = 10000;inline void matrix_multiply(int A[N][N], int B[N][N], int C[N][N])
{for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {C[i][j] = 0;for (int k = 0; k < N; ++k) {C[i][j] += A[i][k] * B[k][j] % MASK;C[i][j] %= MASK;}}}
}void matrix_power(int n, int M[N][N], int P[N][N])
{if (n == 0) {memset(P, 0, sizeof(int)*N*N);for (int i = 0; i < N; ++i)P[i][i] = 1;} else {int Q[N][N], A[N][N];matrix_power(n>>1, M, Q);matrix_multiply(Q, Q, A);if (n&1)matrix_multiply(A, M, P);elsememcpy(P, A, sizeof(int)*N*N);}
}int main()
{int n;scanf("%d", &n);while (n != -1) {if (n == 0)puts("0");else if (n == 1)puts("1");else {int M[2][2] = {
   0, 1, 1, 1}, P[2][2];matrix_power(n-1, M, P);printf("%d\n", P[1][1]);}scanf("%d", &n);}return 0;
}