把 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
形式化题目
设斐波那契数列
求
有多组询问,
正解
思路
先看朴素做法为什么不行。 最直接的做法是枚举
稍微聪明一点的做法是先统计"下标和
破局点:把斐波那契项写成矩阵幂,让求和号可以直接穿进去。
先做下标平移,令
取标准转移矩阵
于是
所以
原来纠缠在一起的
把
于是每组询问只需要:先用矩阵快速幂算
正确性。 推导只用到两个事实:
边界。
实现坑。 main.cpp 里对这两个位置做了 +MOD 处理,
main.py 则靠 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++ 版(同一算法):
// 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;
}复杂度
- 时间:每组询问两次
矩阵快速幂,分别为 与 次矩阵乘法,每次乘法常数级。总时间 , 对 只有几千次标量乘法,实测( main.cpp) 在 10 个真实数据点上全部远低于限时 1000 ms。 - 空间:只用常数个
矩阵, 。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法,只是把矩阵按行压成 四元组以省掉下标。Python 的常数比 C++ 大一个量级,但本题运算量极小, 不存在 Python 特有的 TLE 风险。
总结
- 线性递推的项 = 矩阵的幂:把
换成 的元素,求和对象就从数 升级成矩阵,这是本题唯一需要的"换视角"。 - 可交换才能拆求和号:
重求和能拆成 ,全靠 的各次幂可交换。 换成一般矩阵这一步就不成立,所以要特意把同底数幂聚到一起。 - 前缀和让
一步到位: 把 项矩阵和压成三个 斐波那契数的组合,不必真的做 次矩阵加法。 - 公式自带边界:
得到单位矩阵、 退化成前缀和,两处都不用特判。 - 本题来自信息学奥赛一本通(高手训练·数学基础)。需要注明:素材源中带数据生成脚本
(
data.py,由 cyaron 生成 10 个测试点),说明data/是自造数据、题面为重建版本, 出题意图可能与原题有偏差;std.cpp也是按题面自研的闭式矩阵写法(注释中写明未找到 外部参考)。本地已验证std.cpp与本文解法在全部 10 个数据点上一致, 且两者都在小规模上与暴力枚举、中规模上与独立的下标和计数 DP 吻合。