🔗 UVA-10229 Modular Fibonacci

tags: `快速冪`, `矩陣快速冪`, `線性代數(Linear Algebra)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

令 Fibonacci 數列 $F_0 = 0, F_1 = 1$ ，並定義 $F_n = F_{n-1} + F_{n-2}$ 。

給定 $n$ 和 $m$ ，求 $F_n \mod 2^m$ 。

約束條件

$0 \leq n \leq 2147483647$
$1 \leq m \leq 20$ 。

LuckyCat 的中文翻譯

思路：矩陣快速冪、線性代數(Linear Algebra)

對於這麼大的 $n$ ，若直接使用遞迴式計算 Fibonacci 數列，就算使用了記憶化(Memoization)，時間複雜度也還是需要 $O(n)$ ，這顯然是不可行的，因此需要找到比 $O(n)$ 更快的方法。

由於 Fibonacci 數列是遞迴式的，因此可以將遞迴式轉換成矩陣乘法，如下所示：

$\begin{aligned} \left[\begin{array}{c} F_{n+1} \\ F_n \end{array}\right] & = \left[\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right] \times \left[\begin{array}{c} F_n \\ F_{n-1} \end{array}\right] \\ & =\left[\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right] \times \ldots \times \left[\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right] \times \left[\begin{array}{l} F_1 \\ F_0 \end{array}\right] \\ & = \left[\begin{array}{ll} 1 & 1 \\ 1 & 0 \end{array}\right] ^n \times \left[\begin{array}{l} F_1 \\ F_0 \end{array}\right] \end{aligned}$

如此便可以將求 $F_n$ 轉換成求 $\left[\begin{array}{l} 1 & 1 \\ 1 & 0 \end{array}\right]^n$ ，這是一個矩陣的 $n$ 次方，而對於求 $n$ 次方，可以使用快速冪的方式。

定義一個 Matrix 類別，並重載乘法運算子(__mul__, *)，使其可以進行矩陣乘法運算，再使用快速冪的方式計算 $F_n$ 。由於矩陣大小只有 $2 \times 2$ ，這裡直接使用 $\left[\begin{array}{l} a & b \\ c & d \end{array}\right]$ 作為矩陣的表示方式，並在初始化時傳入 $a, b, c, d$ 和 $mask$ 。其中 $mask = 2^m - 1$ ，將 $x$ 對 $2^m$ 取餘數，即 $x \mod 2^m$ ，可以使用 $x \And \text{mask}$ 來實現。

複雜度分析

時間複雜度： $O(\log n)$
空間複雜度： $O(1)$

class Matrix:
    def __init__(self, a, b, c, d, mask):
        self.a, self.b, self.c, self.d = a, b, c, d
        self.mask = mask

    def __mul__(self, other): # operator *
        return Matrix(
            (self.a * other.a + self.b * other.c) & self.mask,
            (self.a * other.b + self.b * other.d) & self.mask,
            (self.c * other.a + self.d * other.c) & self.mask,
            (self.c * other.b + self.d * other.d) & self.mask,
            self.mask
        )

while True:
    try:
        n, m = map(int, input().split())
    except EOFError:
        break
    M = Matrix(1, 1, 1, 0, (1 << m )- 1)
    X = Matrix(1, 0, 0, 0, (1 << m )- 1)
    while n: # exponentiation by squaring
        if n & 1:
            X = X * M
        M = M * M
        n >>= 1
    print(X.b)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

class Matrix {
public:
    int a, b, c, d, mask;
    Matrix(int a, int b, int c, int d, int mask) : a(a), b(b), c(c), d(d), mask(mask) {}
    Matrix operator*(const Matrix &other) {
        return Matrix(
            (a * other.a + b * other.c) & mask,
            (a * other.b + b * other.d) & mask,
            (c * other.a + d * other.c) & mask,
            (c * other.b + d * other.d) & mask,
            mask
        );
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        Matrix M(1, 1, 1, 0, (1 << m) - 1);
        Matrix X(1, 0, 0, 0, (1 << m) - 1);
        while (n) {
            if (n & 1) X = X * M;
            M = M * M;
            n >>= 1;
        }
        cout << X.b << endl;
    }
    return 0;
}