k-斐波那契数列与矩阵快速幂

问题：定义数列 (F)：

• 前 (k) 项均为 1：(F_1 = F_2 = \cdots = F_k = 1)
• 第 (n) 项（(n > k)）为前 (k) 个相邻项之和：(F_n = F_{n-1} + F_{n-2} + \cdots + F_{n-k})

求 (F_n) 的值（(n) 和 (k) 可能很大，需要快速计算）。

当 (k=2) 时即为经典斐波那契数列。

一、问题本质：线性递推

递推式是线性、齐次的，只依赖前 (k) 项。这种递推都可以写成「状态向量 × 转移矩阵」的形式，从而用矩阵快速幂把「逐项递推」变成「矩阵的 ((n-k)) 次幂」，将单次求 (F_n) 的时间从 (O(n)) 降到 (O(k^3 \log n))。

二、朴素做法为什么慢

直接按定义递推：

1
2
3

F[1..k] = 1
for i from k+1 to n:
    F[i] = F[i-1] + F[i-2] + ... + F[i-k]

• 时间：(O(n))，(n) 很大时不可接受。
• 空间：可以只保留最近 (k) 个数，(O(k))。

若 (n = 10^9)、(k = 10)，显然不能真的循环 (10^9) 次，需要把「递推 (n-k) 步」变成「做 (\log(n-k)) 次矩阵乘法」。

三、状态向量与转移矩阵

3.1 状态向量

递推只依赖「当前连续 (k) 个数」，因此用长度为 (k) 的向量表示「状态」：

[
\mathbf{v}n =
\begin{bmatrix} F_n \ F{n-1} \ F_{n-2} \ \vdots \ F_{n-k+1} \end{bmatrix}
]

也就是说，(\mathbf{v}n) 的第 0 个分量就是 (F_n)，后面依次是 (F{n-1},, F_{n-2},, \ldots,, F_{n-k+1})。

3.2 下一步状态

递推一步后：

• 新的「当前项」为：(F_{n+1} = F_n + F_{n-1} + \cdots + F_{n-k+1})，即 (\mathbf{v}_n) 的 (k 个分量之和)。
• 新的「前一项」为 (F_n)，即原 (\mathbf{v}_n) 的第 0 个分量。
• 再往前依次是 (F_{n-1},, F_{n-2},, \ldots,, F_{n-k+2})，都来自 (\mathbf{v}_n) 的前 (k-1) 个分量依次下移一位。

因此：

[
\mathbf{v}{n+1} =
\begin{bmatrix} F{n+1} \ F_n \ F_{n-1} \ \vdots \ F_{n-k+2} \end{bmatrix}

\begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \
1 & 0 & 0 & \cdots & 0 \
0 & 1 & 0 & \cdots & 0 \
\vdots & \ddots & \ddots & \ddots & \vdots \
0 & \cdots & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix} F_n \ F_{n-1} \ F_{n-2} \ \vdots \ F_{n-k+1} \end{bmatrix}
= M \mathbf{v}_n
]

3.3 转移矩阵 (M) 的结构

(M) 是 (k \times k) 矩阵：

• 第 0 行：全 1，表示 (F_{n+1} = F_n + F_{n-1} + \cdots + F_{n-k+1})。
• 第 1 行：([1,0,\ldots,0])，表示新状态的「前一项」= 原 (F_n)。
• 第 2 行：([0,1,0,\ldots,0])，表示再前一项 = 原 (F_{n-1})。
• 以此类推，第 (i) 行（(i \ge 1)）只有第 (i-1) 列为 1，其余为 0。

即：

[
M =
\begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \
1 & 0 & 0 & \cdots & 0 \
0 & 1 & 0 & \cdots & 0 \
\vdots & \ddots & \ddots & \ddots & \vdots \
0 & \cdots & 0 & 1 & 0
\end{bmatrix}
]

于是：

[
\mathbf{v}n = M \mathbf{v}{n-1} = M^2 \mathbf{v}_{n-2} = \cdots = M^{n-k} \mathbf{v}_k
]

3.4 初始向量 (\mathbf{v}_k)

当 (n = k) 时，状态为 ([F_k,, F_{k-1},, \ldots,, F_1]^T)，由定义 (F_1 = \cdots = F_k = 1)，故：

[
\mathbf{v}_k = [1,, 1,, \ldots,, 1]^T
]

因此：

[
\mathbf{v}_n = M^{n-k} \mathbf{v}_k
]

(F_n) 即为 (\mathbf{v}_n) 的第 0 个分量，也就是 (M^{n-k}) 的第 0 行与 (\mathbf{v}_k) 的内积。由于 (\mathbf{v}_k) 全为 1，即：

[
F_n = \sum_{j=0}^{k-1} (M^{n-k})_{0,j}
]

也就是说：先算 (M^{n-k})，再取第 0 行所有元素之和即可得到 (F_n)。

四、矩阵快速幂

要算 (M^{n-k})，用快速幂思想：

• (M^0 = I)（单位矩阵）
• (M^{2t} = (M^t)^2)
• (M^{2t+1} = M \cdot M^{2t})

每次乘法是 (k \times k) 矩阵乘 (k \times k)，单次 (O(k^3))；指数 (n-k) 的二进制长度为 (O(\log n))，故乘法次数 (O(\log n))。

总时间复杂度：(O(k^3 \log n))。
若要对 (10^9+7) 取模，在矩阵运算中每一步对模数取模即可。

五、算法流程小结

1. 若 (n \le k)：直接返回 1。
2. 若 (n > k)：
   • 构造 (k \times k) 转移矩阵 (M)（第 0 行全 1，第 (i) 行仅第 (i-1) 列为 1，(i \ge 1)）。
   • 计算 (P = M^{n-k})（矩阵快速幂）。
   • (F_n = \sum_{j=0}^{k-1} P_{0,j})（对模数取模）。

六、代码实现（Python，含取模）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

MOD = 10**9 + 7

def mat_mult(A, B):
    """k×k 矩阵乘法 (A * B)，结果对 MOD 取模"""
    k = len(A)
    C = [[0] * k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            for t in range(k):
                C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD
    return C

def mat_pow(M, exp):
    """矩阵快速幂 M^exp"""
    k = len(M)
    base = [row[:] for row in M]
    res = [[1 if i == j else 0 for j in range(k)] for i in range(k)]
    while exp:
        if exp & 1:
            res = mat_mult(res, base)
        base = mat_mult(base, base)
        exp >>= 1
    return res

def k_fib(n, k):
    """
    前 k 项为 1，每项为前 k 项之和，求 F_n (对 MOD 取模)。
    n, k 从 1 开始计数。
    """
    if n <= k:
        return 1
    # 构造 k×k 转移矩阵 M
    M = [[0] * k for _ in range(k)]
    M[0] = [1] * k
    for i in range(1, k):
        M[i][i - 1] = 1
    # F_n = (M^(n-k) 的第 0 行) 与 [1,1,...,1] 的内积
    P = mat_pow(M, n - k)
    Fn = sum(P[0][j] for j in range(k)) % MOD
    return Fn


# ---------- 验证 ----------
# k=2 即普通斐波那契: 1,1,2,3,5,8,13,21,34,55,...
assert k_fib(1, 2) == 1 and k_fib(2, 2) == 1 and k_fib(10, 2) == 55

# k=3: 1,1,1,3,5,9,17,31,57,...
assert k_fib(1, 3) == 1 and k_fib(3, 3) == 1 and k_fib(4, 3) == 3 and k_fib(5, 3) == 5

七、小例子：k=2（普通斐波那契）

状态向量为 (\mathbf{v}n = [F_n,, F{n-1}]^T)，转移矩阵：

[
M = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}
]

初始 (\mathbf{v}_2 = [1,, 1]^T)。
例如求 (F_5)：(\mathbf{v}_5 = M^{5-2} \mathbf{v}_2 = M^3 [1,,1]^T)。

[
M^3 = M \cdot M^2 = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}
\begin{bmatrix} 2 & 1 \ 1 & 1 \end{bmatrix}
= \begin{bmatrix} 3 & 2 \ 2 & 1 \end{bmatrix}
]

(F_5 = 3 \cdot 1 + 2 \cdot 1 = 5)，与定义一致。

八、推广：任意线性递推

凡是形如：

[
a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}
]

的线性齐次递推，都可以写成 (\mathbf{v}n = M \mathbf{v}{n-1})，其中 (\mathbf{v}n = [a_n,, a{n-1},, \ldots,, a_{n-k+1}]^T)，(M) 的第一行是 ([c_1,, c_2,, \ldots,, c_k])，其余行是「单位下移」（第 (i) 行第 (i-1) 列为 1）。再用矩阵快速幂即可 (O(k^3 \log n)) 求 (a_n)。k-斐波那契只是 (c_1 = c_2 = \cdots = c_k = 1) 的特例。

九、复杂度与注意点

小结：k-斐波那契是「前 k 项为 1、每项为前 k 项和」的线性递推。用状态向量 (+) 转移矩阵写成 (\mathbf{v}_n = M^{n-k} \mathbf{v}_k)，再对 (M) 做快速幂，即可在 (O(k^3 \log n)) 内求 (F_n)。同一套思路适用于所有线性齐次递推。