递推数列

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

把分式线性递推看作莫比乌斯变换,用齐次坐标转成 2x2 矩阵,矩阵快速幂求第 n 项,扩欧求逆元。

OJ: roj

题目 ID: 1798

难度:提高

标签:数学矩阵快速幂莫比乌斯变换逆元python

创建: 2026-10-08 03:50

更新: 2026-10-08 03:50

形式化题目

多组数据。每组给定整数 f(0),a,b,c,d,n,pf(0), a, b, c, d, n, p,其中数列满足

f(i)≡a⋅f(i−1)+bc⋅f(i−1)+d(modp), f(i) \equiv \frac{a \cdot f(i-1) + b}{c \cdot f(i-1) + d} \pmod p ,

求 f(n) mod pf(n) \bmod p(结果取 [0,p)[0, p) 内的非负整数)。这里的除法指模 pp 意义下的乘法逆元, 题面保证求逆元时分母与 pp 互素;也保证 0⩽∣f(0)∣,∣a∣,∣b∣,∣c∣,∣d∣<p0 \leqslant |f(0)|, |a|, |b|, |c|, |d| < p, 即系数可以是负数(样例里就有 d=−40d = -40)。

约束:1⩽t⩽1041 \leqslant t \leqslant 10^4,0⩽n⩽10180 \leqslant n \leqslant 10^{18},2⩽p⩽1092 \leqslant p \leqslant 10^9。

正解

思路

朴素做法。 从 f(1)f(1) 开始逐项套公式算到 f(n)f(n),每步做几次模乘加和一次求逆元。 单组数据是 O(nlog⁡p)O(n \log p),看上去没问题;但 nn 可以到 101810^{18},而组数又有 10410^4 组, 总复杂度 O(t⋅n)O(t \cdot n) 是 102210^{22} 量级,完全是天文数字。问题出在"逐项"这一步: nn 那么大时,必须找一种能跳跃式求出第 nn 项的办法。

突破口:分式线性变换就是莫比乌斯变换。 把 f(i)f(i) 写成分子分母两个数之比, 令

f(i)=xiyi,x0=f(0),y0=1. f(i) = \frac{x_i}{y_i}, \qquad x_0 = f(0),\quad y_0 = 1 .

代回递推式,把 f(i−1)=xi−1/yi−1f(i-1) = x_{i-1} / y_{i-1} 通分:

f(i)=a⋅xi−1yi−1+bc⋅xi−1yi−1+d=a xi−1+b yi−1c xi−1+d yi−1. f(i) = \frac{a \cdot \dfrac{x_{i-1}}{y_{i-1}} + b} {c \cdot \dfrac{x_{i-1}}{y_{i-1}} + d} = \frac{a\, x_{i-1} + b\, y_{i-1}} {c\, x_{i-1} + d\, y_{i-1}} .

这就说明:新状态 (xi,yi)(x_i, y_i) 关于旧状态 (xi−1,yi−1)(x_{i-1}, y_{i-1}) 是线性的——

xi=a xi−1+b yi−1,yi=c xi−1+d yi−1. x_i = a\, x_{i-1} + b\, y_{i-1}, \qquad y_i = c\, x_{i-1} + d\, y_{i-1} .

原来那个非线性的分式递推,在把"一个值"拆成"分子、分母一对数"(齐次坐标)之后, 就变成了线性映射,于是可以写成矩阵形式:

(xiyi)=(abcd)(xi−1yi−1). \begin{pmatrix} x_i \\ y_i \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x_{i-1} \\ y_{i-1} \end{pmatrix} .

为什么要拆成分子分母? 因为分式整体上不是线性的(分子分母同时在动), 但它的"齐次版本"是线性的。这正是射影几何里莫比乌斯变换的标准做法: 2×22 \times 2 矩阵作用在齐次坐标上,两个状态只要成比例就代表同一个值, 所以迭代 nn 次就等于把这个矩阵自乘 nn 次。

为什么不走别的路? 两条备选都被约束掐死了:

  1. 找模 pp 下的周期:pp 可以到 10910^9,变换的状态空间(非零点对)高达 O(p2)O(p^2), 周期本身就可能很长,无法枚举。
  2. 解特征方程求通项:需要开平方(二次剩余),在 Fp\mathbb{F}_p 里可能无解, 得扩到二次扩域并处理重根、判别式为零等一堆特判,实现复杂且容易错。

矩阵快速幂则完全通用:不关心 pp 是不是素数、判别式有没有平方根、有没有重根, 模板只有十几行。

正解步骤。

  1. 把 (f(0),1)(f(0), 1) 当作初始状态向量,M=(abcd)M = \begin{pmatrix} a & b \\ c & d \end{pmatrix}。
  2. 由上面的归纳(f(i)=xi/yif(i) = x_i / y_i,i=1i = 1 时直接成立,i>1i > 1 由通分归纳)得
(xnyn)=M n(f(0)1). \begin{pmatrix} x_n \\ y_n \end{pmatrix} = M^{\,n} \begin{pmatrix} f(0) \\ 1 \end{pmatrix} .
  1. 用矩阵快速幂(二进制拆分)在 O(log⁡n)O(\log n) 次 2×22 \times 2 乘法内算出 MnM^n。
  2. 算出 (xn,yn)(x_n, y_n),答案即 xn⋅yn−1 mod px_n \cdot y_n^{-1} \bmod p。逆元用扩展欧几里得, 这样 pp 不是素数也照样能算(题面只保证逆元存在,没说 pp 是素数)。
  3. n=0n = 0 时矩阵零次幂是单位阵,向量还是 (f(0),1)(f(0), 1),答案就是 f(0) mod pf(0) \bmod p, 与公式自洽,不需要特判(但代码里顺手短路一下更省常数)。

代码

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: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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:单组数据做一次矩阵快速幂,O(log⁡n)O(\log n) 次矩阵乘法,每次 8 个标量乘法; 再算一次逆元 O(log⁡p)O(\log p)。总计 O(t(log⁡n+log⁡p))O(t(\log n + \log p))。 取 t=104t = 10^4、n=1018n = 10^{18} 时约 10610^6 次标量模乘,1 s 限时下余量充足。
  • 空间:矩阵、向量都是常数个 2×22 \times 2 / 长度 2 的数组,O(1)O(1)。
  • 与 C++ 解法的关系:main.cpp 与 main.py 算法完全一致,只是把 tuple 换成 结构体数组、把 pow(y, -1, p) 换成手写扩欧。t=104t = 10^4 组、n=1018n = 10^{18} 的 极限数据下 Python 约需 3 s,存在 TLE 风险(该 skill 允许 Python 慢), 但算法与 C++ 同阶,没有做任何降级。

总结

  • 非线性靠升维化解:分式递推 ax+bcx+d\frac{ax+b}{cx+d} 整体非线性,但用齐次坐标 (x,y)(x, y) 表示"比值"之后,递推就变成矩阵乘法——把"值"换成"成比例的一对数", 这是射影变换的通用套路。
  • 求第 nn 项 = 矩阵幂:凡是"每步都是同一个线性变换"的递推,nn 大时一律 用二进制快速幂降到 O(log⁡n)O(\log n),不要去找周期或通项。
  • 逆元用扩欧更稳:题面只保证逆元存在,没保证 pp 是素数,因此不要默认用 费马小定理;pow(y, -1, p) 在 Python 中同样只依赖 gcd⁡(y,p)=1\gcd(y, p) = 1。
  • 负数系数先规范化:读入后立刻 % p 到非负区间,否则乘法取模会得到负数。
  • 溢出:p⩽109<230p \leqslant 10^9 < 2^{30},两数相乘 <260< 2^{60},两项相加 <261< 2^{61}, long long 足够,但要记得全程用 64 位。

数据来源说明:本题素材目录里带有数据生成脚本 data.py / data.json, 说明 data/ 下的 10 个测试点是由该脚本配合 std.cpp 自助生成的, 题面本身也像是从公开题(信息学奥赛一本通 · 高手训练篇)重建而来, 因此测试强度与官方原始数据可能存在偏差(例如官方数据里可能包含 pp 非素数、 中间分母为 00 等更刁钻的边界)。本解按题面给出的保证(逆元存在)实现, 用扩展欧几里得求逆元,对 pp 是否为素数均鲁棒。