ZeroJudge 解題筆記：a451. 10229 - Modular Fibonacci

作者：王一哲
日期：2025年12月30日


ZeroJudge 題目連結：a451. 10229 - Modular Fibonacci

解題想法

這題要用到矩陣乘法與費氏數列的關係，假設第 $n$ 項的費氏數列為 $F(n)$，則 $$ F(0) = 0, ~F(1) = 1, ~F(2) = F(1) + F(0) = 1, \dots, F(n) = F(n-1) + F(n-2) $$ 改用矩陣乘法可以寫成 $$ \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} =\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} F(n-1) \\ F(n-2) \end{bmatrix} $$ 假設 $$ M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} $$ 上式可以改寫成 $$ \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix} =M^{n-1} \begin{bmatrix} F(1) \\ F(0) \end{bmatrix} $$
為了快速地計算 $M^n$，需要用到快速冪。一開始需要用一個二階單位矩陣 $$ I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} $$ 再用單位矩陣乘以 $M^n$。如果 $n$ 是偶數，則 $$ M^n = M^{\frac{n}{2}} M^{\frac{n}{2}} $$ 如果 $n$ 是奇數，則 $$ M^n = M M^{\frac{n-1}{2}} M^{\frac{n-1}{2}} $$ 由於題目要將 $F(n)$ 對 $2^m$ 取餘數，在計算 $M^n$ 的過程中同時就要取餘數，才不會讓數值過大。

Python 程式碼

使用時間約為 1.1 s，記憶體約為 4.2 MB，通過測試。

import sys

def matmul(a, b, mod):
    return [[(a[0][0]*b[0][0] + a[0][1]*b[1][0])%mod, (a[0][0]*b[0][1] + a[0][1]*b[1][1])%mod],
            [(a[1][0]*b[0][0] + a[1][1]*b[1][0])%mod, (a[1][0]*b[0][1] + a[1][1]*b[1][1])%mod]]

def mat_pow(mat, power, mod):
    result = [[1, 0], [0, 1]]
    while power:
        if power&1:
            result = matmul(result, mat, mod)
        mat = matmul(mat, mat, mod)
        power >>= 1
    return result

def solve(n, m):
    if n == 0: return 0
    mod = 2**m
    if n == 1: return 1%mod
    mat = [[1, 1], [1, 0]]
    return mat_pow(mat, n-1, mod)[0][0] % mod

for line in sys.stdin:
    print(solve(*map(int, line.split())))

C++ 程式碼

使用時間約為 0.1 s，記憶體約為 284 kB，通過測試。

#include <cstdio>
#include <vector>
typedef long long LL;
using namespace std;

LL quick_pow(LL base, LL power) {
    LL result = 1;
    while(power) {
        if (power&1) result *= base;
        base *= base;
        power >>= 1;
    }
    return result;
}

vector<vector<LL>> matmul(vector<vector<LL>>& a, vector<vector<LL>>& b, LL mod) {
    vector<vector<LL>> result (2, vector<LL> (2, 0));
    result[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[1][0])%mod;
    result[0][1] = (a[0][0]*b[0][1] + a[0][1]*b[1][1])%mod;
    result[1][0] = (a[1][0]*b[0][0] + a[1][1]*b[0][1])%mod;
    result[1][1] = (a[1][0]*b[0][1] + a[1][1]*b[1][1])%mod;
    return result;
}

vector<vector<LL>> mat_pow(vector<vector<LL>>& mat, LL power, LL mod) {
    vector<vector<LL>> result = {{1, 0}, {0, 1}};
    while(power) {
        if (power&1) result = matmul(result, mat, mod);
        mat = matmul(mat, mat, mod);
        power >>= 1;
    }
    return result;
}

LL solve(LL n, LL m) {
    if (n == 0) return 0;
    LL mod = quick_pow(2, m);
    if (n == 1) return 1%mod;
    vector<vector<LL>> mat = {{1, 1}, {1, 0}};
    return mat_pow(mat, n-1, mod)[0][0] % mod;
}

int main() {
    LL n, m;
    while(scanf("%lld %lld", &n, &m) != EOF) {
        printf("%lld\n", solve(n, m));
    }
    return 0;
}