思路与算法

将一次线性分式变换表示为矩阵[[a,b],[c,d]]，连续n次变换对应矩阵n次幂。对负系数先归一到0..p-1，快速幂后计算分子Af0+B及分母Cf0+D。p不保证质数，用扩展欧几里得求分母的模逆元后相乘。

正确性说明

线性分式变换复合的分子分母展开正是矩阵乘法，因此n次幂准确表示迭代。题目保证逐步分母可逆，合成分母等于逐步分母的乘积，也必是单位，所以扩欧能求逆。n=0时单位矩阵给出原值。

复杂度

每组初始化O(1)，2阶快速幂O(logn)，扩欧O(logp)，总O(logn+logp)时间、O(logp)递归空间。乘法中两项之和<2p²，用64位可容纳p≤1e9。

易错点

不能用费马小定理替代扩欧，模数可能为合数。负余数必须归一化。不要把线性分式按实数除法执行。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
long long eg(long long a, long long b, long long &x, long long &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    long long u, v, g = eg(b, a % b, u, v);
    x = v;
    y = u - a / b * v;
    return g;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        long long f, a, b, c, d, n, p;
        cin >> f >> a >> b >> c >> d >> n >> p;
        auto norm = [&](long long x) {
            return (x % p + p) % p;
        };
        array<long long, 4> M = {norm(a), norm(b), norm(c), norm(d)}, R = {1, 0, 0, 1};
        auto mul = [&](array<long long, 4> x, array<long long, 4> y) {
            return array<long long, 4>{
                (x[0] * y[0] + x[1] * y[2]) % p, (x[0] * y[1] + x[1] * y[3]) % p,
                (x[2] * y[0] + x[3] * y[2]) % p, (x[2] * y[1] + x[3] * y[3]) % p};
        };
        while (n) {
            if (n & 1)
                R = mul(R, M);
            M = mul(M, M);
            n >>= 1;
        }
        long long u = norm(R[0] * norm(f) + R[1]), v = norm(R[2] * norm(f) + R[3]), x, y;
        eg(v, p, x, y);
        cout << u * norm(x) % p << '\n';
    }
}