把分式线性递推看作莫比乌斯变换,用齐次坐标转成 2x2 矩阵,矩阵快速幂求第 n 项,扩欧求逆元。
OJ: roj
题目 ID: 1798
难度:提高
标签:数学矩阵快速幂莫比乌斯变换逆元python
创建: 2026-10-08 03:50
更新: 2026-10-08 03:50
形式化题目
多组数据。每组给定整数
求
约束:
正解
思路
朴素做法。 从
突破口:分式线性变换就是莫比乌斯变换。 把
代回递推式,把
这就说明:新状态
原来那个非线性的分式递推,在把"一个值"拆成"分子、分母一对数"(齐次坐标)之后, 就变成了线性映射,于是可以写成矩阵形式:
为什么要拆成分子分母? 因为分式整体上不是线性的(分子分母同时在动),
但它的"齐次版本"是线性的。这正是射影几何里莫比乌斯变换的标准做法:
为什么不走别的路? 两条备选都被约束掐死了:
- 找模
下的周期: 可以到 ,变换的状态空间(非零点对)高达 , 周期本身就可能很长,无法枚举。 - 解特征方程求通项:需要开平方(二次剩余),在
里可能无解, 得扩到二次扩域并处理重根、判别式为零等一堆特判,实现复杂且容易错。
矩阵快速幂则完全通用:不关心
正解步骤。
- 把
当作初始状态向量, 。 - 由上面的归纳(
, 时直接成立, 由通分归纳)得
- 用矩阵快速幂(二进制拆分)在
次 乘法内算出 。 - 算出
,答案即 。逆元用扩展欧几里得, 这样 不是素数也照样能算(题面只保证逆元存在,没说 是素数)。 时矩阵零次幂是单位阵,向量还是 ,答案就是 , 与公式自洽,不需要特判(但代码里顺手短路一下更省常数)。
代码
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:50
# update_at: 2026-10-08 03:50
import sys
type Matrix = tuple[int, int, int, int] # 2x2 矩阵按行主序压平:[[a,b],[c,d]] -> (a,b,c,d)
def mat_mul(A: Matrix, B: Matrix, p: int) -> Matrix:
"""2x2 矩阵乘法(模 p):展开成 8 次标量乘法,不做循环。"""
return (
(A[0] * B[0] + A[1] * B[2]) % p, (A[0] * B[1] + A[1] * B[3]) % p,
(A[2] * B[0] + A[3] * B[2]) % p, (A[2] * B[1] + A[3] * B[3]) % p,
)
def mat_pow(M: Matrix, e: int, p: int) -> Matrix:
"""矩阵快速幂 M^e:n 可达 1e18,二进制拆分后只需 O(log e) 次乘法。"""
R: Matrix = (1, 0, 0, 1) # 单位矩阵,e = 0(即 n = 0)时答案直接由它还原成 f(0)
while e:
if e & 1:
R = mat_mul(R, M, p)
M = mat_mul(M, M, p)
e >>= 1
return R
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
t = next(data)
out: list[str] = []
for _ in range(t):
f0, a, b, c, d, n, p = (next(data), next(data), next(data),
next(data), next(data), next(data), next(data))
# 系数可能为负(题面 0<=|x|<p),Python 的 % 结果恒非负,直接取模即可
f0 %= p; a %= p; b %= p; c %= p; d %= p
# 齐次坐标:把 f(i) 写成 x_i / y_i,则 (x_i,y_i) = [[a,b],[c,d]]^i (f0,1)
R = mat_pow((a, b, c, d), n, p)
x = (R[0] * f0 + R[1]) % p
y = (R[2] * f0 + R[3]) % p
out.append(str(x * pow(y, -1, p) % p)) # pow(y,-1,p) 只要求 gcd(y,p)=1,不要求 p 是素数
sys.stdout.write('\n'.join(out) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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:50
* update_at: 2026-10-08 03:50
*/
// main.cpp:递推数列 f(i) = (a*f(i-1)+b) / (c*f(i-1)+d) (mod p),求 f(n)。
// 把分式线性变换看作莫比乌斯变换,用齐次坐标 (分子 x, 分母 y) 转成 2x2 矩阵的幂:
// (x_i, y_i)^T = [[a,b],[c,d]]^i (x_0, y_0)^T, f(i) = x_i * inv(y_i)。
// n 达 1e18,用矩阵快速幂 O(log n);逆元用扩展欧几里得(p 不保证是素数)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXT = 10000 + 5; // 数据组数上界,本题不需要存下来,仅作规模备注
ll p; // 当前这组数据的模数
ll f0, a, b, c, d; // 当前这组数据的初值与四个系数
ll n; // 当前这组数据要求的目标下标
// 把任意整数规范到 [0, p),系数可能为负(题面 0<=|x|<p)
static inline ll norm(ll x) {
x %= p;
if (x < 0) x += p;
return x;
}
// 2x2 矩阵:模 p 意义下的幺半群
struct Mat {
ll m[2][2];
};
// 矩阵乘法,p<=1e9<2^30,单项乘积 <2^60,两项求和 <2^61,long long 不溢出
static Mat mul(const Mat &A, const Mat &B) {
Mat C;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
ll s = (A.m[i][0] * B.m[0][j] + A.m[i][1] * B.m[1][j]) % p;
C.m[i][j] = s;
}
}
return C;
}
// 矩阵快速幂:返回 M^e(e 用 unsigned long long,n<=1e18 也在范围内)
static Mat mpow(Mat M, unsigned long long e) {
Mat R; // 单位矩阵
R.m[0][0] = 1; R.m[0][1] = 0;
R.m[1][0] = 0; R.m[1][1] = 1;
while (e) {
if (e & 1ULL) R = mul(R, M);
M = mul(M, M);
e >>= 1;
}
return R;
}
// 扩展欧几里得:返回 gcd(x,y)=1 时 x 的逆元(不要求模数是素数)
static ll exgcd(ll x, ll y, ll &g, ll &h) {
if (y == 0) { g = 1; h = 0; return x; }
ll r = exgcd(y, x % y, h, g);
h -= (x / y) * g;
return r;
}
// 求 a 在模 p 下的逆元,题面保证 gcd(a,p)=1
static ll inv(ll x) {
ll g, h;
exgcd(norm(x), p, g, h);
return norm(g);
}
int main() {
int t;
if (scanf("%d", &t) != 1) return 0;
for (int tc = 0; tc < t; tc++) {
scanf("%lld %lld %lld %lld %lld %lld %lld", &f0, &a, &b, &c, &d, &n, &p);
f0 = norm(f0); a = norm(a); b = norm(b); c = norm(c); d = norm(d);
if (n == 0) { // 0 次迭代,答案就是规范化的 f(0)
printf("%lld\n", f0);
continue;
}
Mat M;
M.m[0][0] = a; M.m[0][1] = b;
M.m[1][0] = c; M.m[1][1] = d;
Mat R = mpow(M, (unsigned long long)n);
// (x_n, y_n) = M^n * (f0, 1)^T
ll x = (R.m[0][0] * f0 + R.m[0][1]) % p;
ll y = (R.m[1][0] * f0 + R.m[1][1]) % p;
printf("%lld\n", x * inv(y) % p);
}
return 0;
}复杂度
- 时间:单组数据做一次矩阵快速幂,
次矩阵乘法,每次 8 个标量乘法; 再算一次逆元 。总计 。 取 、 时约 次标量模乘,1 s 限时下余量充足。 - 空间:矩阵、向量都是常数个
/ 长度 2 的数组, 。 - 与 C++ 解法的关系:
main.cpp与main.py算法完全一致,只是把 tuple 换成 结构体数组、把pow(y, -1, p)换成手写扩欧。组、 的 极限数据下 Python 约需 3 s,存在 TLE 风险(该 skill 允许 Python 慢), 但算法与 C++ 同阶,没有做任何降级。
总结
- 非线性靠升维化解:分式递推
整体非线性,但用齐次坐标 表示"比值"之后,递推就变成矩阵乘法——把"值"换成"成比例的一对数", 这是射影变换的通用套路。 - 求第
项 = 矩阵幂:凡是"每步都是同一个线性变换"的递推, 大时一律 用二进制快速幂降到 ,不要去找周期或通项。 - 逆元用扩欧更稳:题面只保证逆元存在,没保证
是素数,因此不要默认用 费马小定理; pow(y, -1, p)在 Python 中同样只依赖。 - 负数系数先规范化:读入后立刻
% p到非负区间,否则乘法取模会得到负数。 - 溢出:
,两数相乘 ,两项相加 , long long足够,但要记得全程用 64 位。
数据来源说明:本题素材目录里带有数据生成脚本
data.py/data.json, 说明data/下的 10 个测试点是由该脚本配合std.cpp自助生成的, 题面本身也像是从公开题(信息学奥赛一本通 · 高手训练篇)重建而来, 因此测试强度与官方原始数据可能存在偏差(例如官方数据里可能包含非素数、 中间分母为 等更刁钻的边界)。本解按题面给出的保证(逆元存在)实现, 用扩展欧几里得求逆元,对 是否为素数均鲁棒。