K维斐波那契

GitHub跳转原题关系图返回列表

把 k 重求和拆成矩阵幂:答案等于 (Σ_{j=0}^{n-1}M^j)^k 的左上角元素,用两次 2x2 矩阵快速幂做到每组 O(log n+log k)。

OJ: roj

题目 ID: 1797

难度:提高+/省选-

标签:数学矩阵快速幂斐波那契python

创建: 2026-10-08 03:49

更新: 2026-10-08 03:49

形式化题目

设斐波那契数列 F(1)=F(2)=1F(1)=F(2)=1,F(i)=F(i−1)+F(i−2)F(i)=F(i-1)+F(i-2)。给定 n,kn,k,定义 kk 维超立方体 AA:每一维的坐标都在 1∼n1 \sim n 内取值,点 (i1,i2,…,ik)(i_1,i_2,\dots,i_k) 上的值为

A(i1,…,ik)=F(∑p=1kip−k+1).A(i_1,\dots,i_k) = F\left(\sum_{p=1}^{k} i_p - k + 1\right).

求 AA 内全部 nkn^k 个值之和对 109+710^9+7 取模的结果:

S=∑i1=1n∑i2=1n⋯∑ik=1nF(∑p=1kip−k+1)(mod109+7).S = \sum_{i_1=1}^{n}\sum_{i_2=1}^{n}\cdots\sum_{i_k=1}^{n} F\left(\sum_{p=1}^{k} i_p - k + 1\right) \pmod{10^9+7}.

有多组询问,T⩽100T \leqslant 100,n,k⩽109n,k \leqslant 10^9。

正解

思路

先看朴素做法为什么不行。 最直接的做法是枚举 nkn^k 个点,逐点算斐波那契数累加。 当 n,k⩽109n,k \leqslant 10^9 时这个点数本身就是天文数字,连 k=2,n=105k=2,n=10^5 都过不去。

稍微聪明一点的做法是先统计"下标和 s=∑ips=\sum i_p 有多少种取法",再乘上 F(s−k+1)F(s-k+1)。 但 ss 的取值范围到 k⋅n=1018k\cdot n = 10^{18},而且"kk 个 [1,n][1,n] 变量的和等于 ss"的方案数 需要容斥或生成函数才写得出来,同样无法承受。两条路都被"维数没有解耦"卡死了。

破局点:把斐波那契项写成矩阵幂,让求和号可以直接穿进去。

先做下标平移,令 jp=ip−1∈[0,n−1]j_p = i_p - 1 \in [0, n-1],则求和项的下标变成

∑p=1kip−k+1=1+∑p=1kjp.\sum_{p=1}^{k} i_p - k + 1 = 1 + \sum_{p=1}^{k} j_p .

取标准转移矩阵

M=(1110),Mm=(F(m+1)F(m)F(m)F(m−1)),M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \qquad M^m = \begin{pmatrix} F(m+1) & F(m) \\ F(m) & F(m-1) \end{pmatrix},

于是 F(1+∑jp)F\bigl(1+\sum j_p\bigr) 恰好是 M∑jpM^{\sum j_p} 的左上角元素。现在关键的一步: MM 的各次幂彼此可交换,且幂指数可以相加,

Mj1+j2+⋯+jk=Mj1Mj2⋯Mjk,M^{j_1+j_2+\cdots+j_k} = M^{j_1}M^{j_2}\cdots M^{j_k},

所以 kk 重求和可以逐个因子地拆开:

∑j1=0n−1⋯∑jk=0n−1Mj1⋯Mjk=(∑j=0n−1Mj)k=Pk,P=∑j=0n−1Mj.\sum_{j_1=0}^{n-1}\cdots\sum_{j_k=0}^{n-1} M^{j_1}\cdots M^{j_k} = \left(\sum_{j=0}^{n-1} M^j\right)^{k} = P^{k}, \qquad P = \sum_{j=0}^{n-1} M^j .

原来纠缠在一起的 kk 维坐标被彻底解耦:答案就是 PkP^k 的左上角元素。

把 PP 写成 F(n)F(n)、F(n+1)F(n+1)、F(n+2)F(n+2) 的封闭形式。 直接用斐波那契前缀和 ∑r=1xF(r)=F(x+2)−1\sum_{r=1}^{x}F(r) = F(x+2)-1,逐位置加起来就得到

P=(F(n+2)−1F(n+1)−1F(n+1)−1F(n)).P = \begin{pmatrix} F(n+2)-1 & F(n+1)-1 \\ F(n+1)-1 & F(n) \end{pmatrix}.

于是每组询问只需要:先用矩阵快速幂算 MnM^n 取出 F(n+1),F(n)F(n+1),F(n)(左上、右上元素), 由 F(n+2)=F(n+1)+F(n)F(n+2)=F(n+1)+F(n) 补齐,拼出 PP,再对 PP 做一次矩阵快速幂取左上角。

正确性。 推导只用到两个事实:MmM^m 的元素就是斐波那契数(对 mm 归纳即得), 以及同底数幂可交换、指数可加。求和号与矩阵加法的交换是矩阵运算的基本性质, 所以 (∑j=0n−1Mj)k\bigl(\sum_{j=0}^{n-1}M^j\bigr)^k 展开后正好是全部 nkn^k 个 M1+∑jpM^{1+\sum j_p} 的左上角元素之和,即所求的 SS。

边界。 n=1n=1 时 $P = \begin{pmatrix} F(3)-1 & F(2)-1\ F(2)-1 & F(1)\end{pmatrix} = \begin{pmatrix}1&0\0&1\end{pmatrix}$ 是单位矩阵,PkP^k 的左上角恒为 11,与 "只有 F(1)=1F(1)=1 一个元素"一致;k=1k=1 时答案直接是 F(n+2)−1F(n+2)-1,正好是一维前缀和。 两个边界都由公式自动兼容,不需要特判。

实现坑。 F(n+2)−1F(n+2)-1、F(n+1)−1F(n+1)-1 在取模后可能恰为 00,相减要先加模数再取模, 否则会出现负数;矩阵乘法的中间量是 109×109=101810^9 \times 10^9 = 10^{18} 量级, 必须全程用 64 位整数(Python 无此问题)。main.cpp 里对这两个位置做了 +MOD 处理, main.py 则靠 Python 对负数取模返回非负余数的语义天然规避。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 03:47
# update_at: 2026-10-08 03:47

import sys

MOD = 1000000007  # 题目要求的模数

# 类型别名:2x2 矩阵按行压成四元组 (a00, a01, a10, a11),省掉嵌套容器的下标噪声
type Mat = tuple[int, int, int, int]


def mul(x: Mat, y: Mat) -> Mat:
    """两个 2x2 矩阵的乘积(模 MOD)。"""
    a, b, c, d = x
    e, f, g, h = y
    return ((a * e + b * g) % MOD, (a * f + b * h) % MOD,
            (c * e + d * g) % MOD, (c * f + d * h) % MOD)


def mpow(base: Mat, e: int) -> Mat:
    """矩阵 base 的 e 次幂(模 MOD),e 可达 1e9。"""
    res: Mat = (1, 0, 0, 1)  # 单位矩阵
    while e:
        if e & 1:
            res = mul(res, base)
        base = mul(base, base)
        e >>= 1
    return res


def kdim_sum(n: int, k: int) -> int:
    """一组询问的答案:n^k 个元素之和 = (Σ_{j=0}^{n-1} M^j)^k 的左上角元素。"""
    fn1, fn = mpow((1, 1, 1, 0), n)[:2]  # M^n 的左上/右上 = F(n+1), F(n)
    fn2 = (fn1 + fn) % MOD              # F(n+2) = F(n+1) + F(n)
    # P = Σ_{j=0}^{n-1} M^j = [[F(n+2)-1, F(n+1)-1], [F(n+1)-1, F(n)]]
    # Python 的 % 对负数已返回非负余数,F(·)-1 为负时无需额外处理
    p: Mat = ((fn2 - 1) % MOD, (fn1 - 1) % MOD, (fn1 - 1) % MOD, fn)
    return mpow(p, k)[0]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    out: list[int] = []
    for _ in range(T):
        n, k = next(data), next(data)
        out.append(kdim_sum(n, k))
    sys.stdout.write('\n'.join(map(str, out)) + '\n')


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
// 1797 K维斐波那契
// 一本通·高手训练(数学基础)  https://roj.ac.cn/problem/1797
//
// 题意:F(1)=F(2)=1, F(i)=F(i-1)+F(i-2)。
//   k 维超立方体 A 每维 1..n,A(i_1..i_k) = F(i_1+...+i_k-k+1),
//   求 A 内全部 n^k 个元素之和对 1e9+7 取模。多组询问 T<=100,n,k<=1e9。
//
// 算法(矩阵快速幂,O(log n + log k)/组):
//   令 M = [[1,1],[1,0]],则 M^m = [[F(m+1),F(m)],[F(m),F(m-1)]],
//   于是 A 中元素 F(1+Σ(i_j-1)) = (M^{Σ(i_j-1)})_{11}。
//   把 k 重求和拆开,因为 M 的各次幂彼此可交换:
//       Σ_{i_1..i_k} M^{Σ(i_j-1)} = (Σ_{j=0}^{n-1} M^j)^k = P^k
//   取 (1,1) 元素即答案。P 用前缀和公式 Σ_{r=1}^{x}F(r)=F(x+2)-1 化简为
//       P = [[F(n+2)-1, F(n+1)-1], [F(n+1)-1, F(n)]]
//   先求 M^n 得到 F(n)、F(n+1),再加出 F(n+2),最后求 P^k 取左上角。
//
// 坑:F(n+2)-1、F(n+1)-1 可能取到 0,做减法要先 +MOD 再取模;矩阵乘法全程 ll。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL;

// 2x2 矩阵,全局结构体便于传参
struct Mat {
    ll a[2][2];
};

// 模意义下的 2x2 矩阵乘法
Mat mul(const Mat &x, const Mat &y) {
    Mat r;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ll s = 0;
            for (int t = 0; t < 2; t++) {
                s = (s + x.a[i][t] * y.a[t][j]) % MOD;
            }
            r.a[i][j] = s;
        }
    }
    return r;
}

// 2x2 矩阵快速幂,指数 e 可达 1e9
Mat mpow(Mat base, ll e) {
    Mat res;                    // 单位矩阵
    res.a[0][0] = 1; res.a[0][1] = 0;
    res.a[1][0] = 0; res.a[1][1] = 1;
    while (e > 0) {
        if (e & 1LL) res = mul(res, base);
        base = mul(base, base);
        e >>= 1;
    }
    return res;
}

// 单组询问:n 为每维长度,k 为维数
ll solve(ll n, ll k) {
    Mat M;                      // 斐波那契转移矩阵
    M.a[0][0] = 1; M.a[0][1] = 1;
    M.a[1][0] = 1; M.a[1][1] = 0;

    Mat Mn = mpow(M, n);        // M^n = [[F(n+1),F(n)],[F(n),F(n-1)]]
    ll fn = Mn.a[0][1];         // F(n)
    ll fn1 = Mn.a[0][0];        // F(n+1)
    ll fn2 = (fn1 + fn) % MOD;  // F(n+2) = F(n+1) + F(n)

    Mat P;                      // P = Σ_{j=0}^{n-1} M^j
    P.a[0][0] = (fn2 - 1 + MOD) % MOD;
    P.a[0][1] = (fn1 - 1 + MOD) % MOD;
    P.a[1][0] = (fn1 - 1 + MOD) % MOD;
    P.a[1][1] = fn % MOD;

    Mat R = mpow(P, k);         // k 维求和 = P 的 k 次方
    return R.a[0][0];
}

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        ll n, k;
        scanf("%lld %lld", &n, &k);
        printf("%lld\n", solve(n, k));
    }
    return 0;
}

复杂度

  • 时间:每组询问两次 2×22\times2 矩阵快速幂,分别为 O(log⁡n)O(\log n) 与 O(log⁡k)O(\log k) 次矩阵乘法,每次乘法常数级。总时间 O(T(log⁡n+log⁡k))O(T(\log n + \log k)), 对 T=100, n,k⩽109T=100,\ n,k\leqslant 10^9 只有几千次标量乘法,实测(main.cpp) 在 10 个真实数据点上全部远低于限时 1000 ms。
  • 空间:只用常数个 2×22\times2 矩阵,O(1)O(1)。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法,只是把矩阵按行压成 四元组以省掉下标。Python 的常数比 C++ 大一个量级,但本题运算量极小, 不存在 Python 特有的 TLE 风险。

总结

  • 线性递推的项 = 矩阵的幂:把 F(⋅)F(\cdot) 换成 M⋅M^{\cdot} 的元素,求和对象就从数 升级成矩阵,这是本题唯一需要的"换视角"。
  • 可交换才能拆求和号:kk 重求和能拆成 (∑Mj)k(\sum M^j)^k,全靠 MM 的各次幂可交换。 换成一般矩阵这一步就不成立,所以要特意把同底数幂聚到一起。
  • 前缀和让 PP 一步到位:∑r=1xF(r)=F(x+2)−1\sum_{r=1}^{x}F(r)=F(x+2)-1 把 nn 项矩阵和压成三个 斐波那契数的组合,不必真的做 O(n)O(n) 次矩阵加法。
  • 公式自带边界:n=1n=1 得到单位矩阵、k=1k=1 退化成前缀和,两处都不用特判。
  • 本题来自信息学奥赛一本通(高手训练·数学基础)。需要注明:素材源中带数据生成脚本 (data.py,由 cyaron 生成 10 个测试点),说明 data/ 是自造数据、题面为重建版本, 出题意图可能与原题有偏差;std.cpp 也是按题面自研的闭式矩阵写法(注释中写明未找到 外部参考)。本地已验证 std.cpp 与本文解法在全部 10 个数据点上一致, 且两者都在小规模上与暴力枚举、中规模上与独立的下标和计数 DP 吻合。