2670. 「NOI2012」随机数生成器 题解

题目分析

题目给出了线性同余生成器（LCG）的递推公式： [ X_{n+1} = (aX_n + c) \bmod m ]

要求计算 $X_n \bmod g$，其中 $n$ 最大可达 $10^{18}$，$m, a, c, X_0$ 最大可达 $10^{18}$。

直接模拟是不可行的，因为 $n$ 太大。

---

核心思路

1. 转化为矩阵乘法

观察递推式： [ X_{n+1} = aX_n + c ]

我们可以将其表示为矩阵形式： [ \begin{pmatrix} X_{n+1} \ 1 \end{pmatrix} = \begin{pmatrix} a & c \ 0 & 1 \end{pmatrix} \begin{pmatrix} X_n \ 1 \end{pmatrix} ]

令 $M = \begin{pmatrix} a & c \\ 0 & 1 \end{pmatrix}$，则有： [ \begin{pmatrix} X_n \ 1 \end{pmatrix} = M^n \begin{pmatrix} X_0 \ 1 \end{pmatrix} ]

2. 快速幂加速

计算 $M^n$ 可以使用矩阵快速幂，时间复杂度 $O(\log n)$。

3. 大数乘法优化

由于 $m, a, c, X_0$ 最大可达 $10^{18}$，两数相乘会超过 128 位整数范围（C++ 中的 long long 是 64 位）。因此不能直接使用普通的乘法，需要使用 快速乘（龟速乘）。

---

快速乘（龟速乘）

当计算 $(a \times b) \bmod m$ 时，如果 $a, b$ 都接近 $10^{18}$，直接相乘会溢出。快速乘的原理类似于快速幂，将乘法转化为加法：

LL mul(LL a, LL b, LL mod) {
    LL res = 0;
    a %= mod;
    b %= mod;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

时间复杂度 $O(\log b)$，在本题中是可以接受的。

---

矩阵快速幂实现

定义矩阵结构体和矩阵乘法：

struct Matrix {
    LL m[2][2];
};

Matrix mul(Matrix a, Matrix b, LL mod) {
    Matrix res;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            res.m[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                // 使用快速乘防止溢出
                res.m[i][j] = (res.m[i][j] + mul(a.m[i][k], b.m[k][j], mod)) % mod;
            }
        }
    }
    return res;
}

Matrix pow_matrix(Matrix a, LL n, LL mod) {
    Matrix res;
    // 单位矩阵
    res.m[0][0] = res.m[1][1] = 1;
    res.m[0][1] = res.m[1][0] = 0;
    
    while (n) {
        if (n & 1) res = mul(res, a, mod);
        a = mul(a, a, mod);
        n >>= 1;
    }
    return res;
}

---

完整算法流程

1. 读入 $m, a, c, X_0, n, g$
2. 构造矩阵 $M = \begin{pmatrix} a & c \\ 0 & 1 \end{pmatrix}$
3. 计算 $M^n \bmod m$ 使用矩阵快速幂（注意模数是 $m$）
4. 计算 $X_n = (M^n[0][0] \times X_0 + M^n[0][1]) \bmod m$
5. 输出 $X_n \bmod g$

---

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// 快速乘（龟速乘）
LL mul(LL a, LL b, LL mod) {
    LL res = 0;
    a %= mod;
    b %= mod;
    while (b) {
        if (b & 1) res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}

struct Matrix {
    LL m[2][2];
};

// 矩阵乘法
Matrix mul_matrix(Matrix a, Matrix b, LL mod) {
    Matrix res;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            res.m[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                res.m[i][j] = (res.m[i][j] + mul(a.m[i][k], b.m[k][j], mod)) % mod;
            }
        }
    }
    return res;
}

// 矩阵快速幂
Matrix pow_matrix(Matrix a, LL n, LL mod) {
    Matrix res;
    // 单位矩阵
    res.m[0][0] = res.m[1][1] = 1;
    res.m[0][1] = res.m[1][0] = 0;
    
    while (n) {
        if (n & 1) res = mul_matrix(res, a, mod);
        a = mul_matrix(a, a, mod);
        n >>= 1;
    }
    return res;
}

int main() {
    LL m, a, c, x0, n, g;
    cin >> m >> a >> c >> x0 >> n >> g;
    
    // 构造矩阵
    Matrix M;
    M.m[0][0] = a % m;
    M.m[0][1] = c % m;
    M.m[1][0] = 0;
    M.m[1][1] = 1;
    
    // 计算 M^n
    Matrix Mn = pow_matrix(M, n, m);
    
    // 计算 X_n
    // X_n = (Mn[0][0] * X_0 + Mn[0][1]) mod m
    LL Xn = (mul(Mn.m[0][0], x0, m) + Mn.m[0][1]) % m;
    
    // 输出 X_n mod g
    cout << Xn % g << endl;
    
    return 0;
}

---

数学推导（可选）

其实这个问题也可以用公式直接求解：

对于线性同余生成器： [ X_n = a^n X_0 + c \cdot \frac{a^n - 1}{a - 1} \pmod{m} \quad (a \neq 1) ]

但是：

1. 需要特判 $a = 1$ 的情况
2. 需要处理除法求逆元（要求 $a-1$ 与 $m$ 互质）
3. 同样需要处理大数乘法溢出问题

矩阵方法更加通用，不需要特殊判断 $a=1$ 的情况，也不需要 $a-1$ 与 $m$ 互质。

---

复杂度分析

• 快速乘：$O(\log b)$
• 矩阵乘法：常数次快速乘，$O(\log m)$
• 矩阵快速幂：$O(\log n)$ 次矩阵乘法

总时间复杂度：$O(\log n \cdot \log m)$，可以通过 $n \le 10^{18}$ 的数据。

---

注意事项

1. 模数问题：计算 $M^n$ 时模数是 $m$，最后输出时模数是 $g$
2. 输入输出：所有变量都可能达到 $10^{18}$，使用 long long
3. 快速乘：必须使用快速乘，否则会溢出
4. 初始值：$a, c, X_0$ 可能为 0，需要正确处理

---

总结

这道题考察了：

1. 将线性递推转化为矩阵乘法
2. 矩阵快速幂的应用
3. 处理大数乘法溢出的技巧（快速乘）
4. 模运算的正确使用