POJ 3070 斐波那契数的非矩阵快速幂做法

我们都知道以下公式：

\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix} \tag{1} \]

再通过矩阵快速幂就可以快速计算斐波那契数，但若是没实现好很容易TLE。
这里给出一种新的计算斐波那契数的方法，愿望能起到一种抛砖引玉的作用。

首先将(1)式两边同时平方得：

\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{2n} = \begin{bmatrix} f_{n+1} & f_n \\ f_n & f_{n-1} \end{bmatrix}^2 \]

左边根据(1)式变换，右边矩阵相乘：

\[\begin{bmatrix} f_{2n+1} & f_{2n} \\ f_{2n} & f_{2n-1} \end{bmatrix} = \begin{bmatrix} f_{n+1}^2+f_n^2 & f_n(f_{n+1}+f_{n-1}) \\ f_n(f_{n+1}+f_{n-1}) & f_{n-1}^2+f_n^2 \end{bmatrix} \tag{2} \]

由(2)我们可得以下递推公式：

\[\begin{cases} f_{2n} &= f_n(f_{n+1}+f_{n-1}) \\ \\ f_{2n+1} &= f_{n+1}^2+f_n^2 \end{cases} \]

这样我们就可以避免使用矩阵，下面给出POJ 3070的实现：

#include <map>
#include <cstdio>
using namespace std;
const int mod = 1e4;

map<int, int> dp;

int f(int n)
{
    if(dp.find(n) != dp.end())
        return dp[n];

    int h = n >> 1;

    if(n & 1) {
        int t1 = f(h+1);
        int t2 = f(h);
        t1 = t1 * t1 % mod;
        t2 = t2 * t2 % mod;
        dp[n] = (t1 + t2) % mod;
    } else {
        int t = (f(h-1) + f(h+1)) % mod;
        dp[n] = f(h) * t % mod;
    }
    return dp[n];
}

int main()
{
    int n;
    dp[0] = 0;
    dp[2] = dp[1] = 1;

    while(scanf("%d", &n), ~n)
        printf("%d\n", f(n));
}