作者：王一哲
日期：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())))
