「POJ 3070」Fibonacci - 矩阵乘法

发表于 2022-03-05 更新于 2022-09-04 分类于 OI ，题解阅读次数： 77 Disqus：

题意描述

POJ 链接

给定一个数 $n$ ，求斐波那契数列第 $n$ 项的后四位。

数据范围： $1 \leq n \leq 10^{9}$

解题思路

我们可以使用矩阵来加速地推。

我们知道斐波那契的通项公式为：

$a_{i} = a_{i - 1} + a_{i - 2}$

故我们可以设矩阵 $F (n)$ ：

$F (n) = [\begin{matrix} a_{n} & a_{n + 1} \end{matrix}]$

同时我们可以设：

$F (n) = F (n - 1) \times X$

即为：

$[\begin{matrix} a_{n} & a_{n + 1} \end{matrix}] = [\begin{matrix} a_{n - 1} & a_{n} \end{matrix}] \times X$

我们可以推出：

$[\begin{matrix} a_{n} & a_{n + 1} \end{matrix}] = [\begin{matrix} a_{n - 1} & a_{n} \end{matrix}] \times [\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]$

所以我们最终可以推出下列式子：

$F (n) = F (1) \times {[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]}^{n - 1} = [\begin{matrix} 1 & 1 \end{matrix}] \times {[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}]}^{n - 1}$

最终利用快速幂就可以在 $O (\log n)$ 的时间复杂度中求出答案。

代码演示

#include <cstdio>
#include <cstring>
#include <algorithm>

int fib[1 + 1][2 + 1], x[2 + 1][2 + 1];

void init() {
    fib[1][1] = fib[1][2] = 1;
    x[1][1] = 0;
    x[1][2] = x[2][1] = x[2][2] = 1;
}

void mul(int a[][2 + 1], int ax, int ay, int b[][2 + 1], int bx, int by, int ans[][2 + 1], int mod) {
    int s1[2 + 1][2 + 1], s2[2 + 1][2 + 1];
    memcpy(s1, a, sizeof(int) * (ax + 1) * (ay + 1));
    memcpy(s2, b, sizeof(int) * (bx + 1) * (by + 1));

    for (int i = 1; i <= ax; i++) {
        for (int j = 1; j <= by; j++) {
            int sum = 0;
            for (int k = 1; k <= ay; k++) sum = (sum + s1[i][k] * s2[k][j]) % mod;
            ans[i][j] = sum;
        }
    }
}

void pow(int a[][2 + 1], int ax, int ay, int p, int ans[][2 + 1], int mod) {
    int s1[2 + 1][2 + 1];
    memcpy(s1, a, sizeof(int) * (2 + 1) * (2 + 1));
    memset(ans, 0, sizeof(int) * (2 + 1) * (2 + 1));
    for (int i = 1; i <= std::min(ax, ay); i++) ans[i][i] = 1;


    for (; p; p >>= 1) {
        if (p & 1) mul(ans, 2, 2, s1, 2, 2, ans, mod);
        mul(s1, 2, 2, s1, 2, 2, s1, mod);
    }
}

int main() {
    int n;

    while (scanf("%d", &n) != EOF) {
        if (n == -1) break;
        if (n == 0) {
            printf("0\n");
            continue;
        }
        if (n == 1 || n == 2) {
            printf("1\n");
            continue;
        }
        if (n == 3) {
            printf("2\n");
            continue;
        }

        init();
        pow(x, 2, 2, n - 1, x, 10000);
        mul(fib, 1, 2, x, 2, 2, fib, 10000);

        printf("%d\n", fib[1][1]);
    }

    return 0;
}