NOI 2012 隨機數生成器：矩陣快速冪優化線性遞推

NOI 2012 隨機數生成器：矩陣快速冪優化線性遞推

本題要求計算線性同餘生成器的第 n 項：xₙ = (a·xₙ₋₁ + c) mod mod，並輸出 xₙ mod g。直接模擬需 O(n) 時間，對於大 n 會超時。利用矩陣快速冪可將複雜度降至 O(log n)。

遞推關係的矩陣形式

構造狀態向量：

[ xₙ ]   [ a  0 ] [ xₙ₋₁ ]   [ c ]
[ 1  ] = [ c  1 ] [   1    ]   [ 1 ]  (模 mod 運算)

令轉移矩陣 A = [[a, 0], [c, 1]]，則有：

[ xₙ ]   [ a  0 ]ⁿ [ x₀ ]
[ 1  ] = [ c  1 ]  [ 1  ]

關鍵技術難點

1. 雙重取模：先對 mod 取模，再對 g 取模
2. 防止溢出：中間乘法可能超出 64 位整數範圍，需實現快速乘（類似快速冪的取模乘法）

快速乘實現

unsigned long long fast_mul(unsigned long long x, unsigned long long y, unsigned long long mod) {
    unsigned long long res = 0;
    while (y) {
        if (y & 1) res = (res + x) % mod;
        x = (x + x) % mod;
        y >>= 1;
    }
    return res;
}

矩陣快速冪框架

struct Matrix {
    unsigned long long a[2][2];
    Matrix operator*(const Matrix &other, unsigned long long mod) const {
        Matrix res = {{0}};
        for (int i = 0; i < 2; ++i)
            for (int k = 0; k < 2; ++k)
                for (int j = 0; j < 2; ++j)
                    res.a[i][j] = (res.a[i][j] + fast_mul(a[i][k], other.a[k][j], mod)) % mod;
        return res;
    }
};

Matrix fast_pow(Matrix base, unsigned long long exp, unsigned long long mod) {
    Matrix res = {{{1,0},{0,1}}}; // 單位矩陣
    while (exp) {
        if (exp & 1) res = res * base * mod;
        base = base * base * mod;
        exp >>= 1;
    }
    return res;
}

完整求解流程

1. 讀入 mod, a, c, x₀, n, g
2. 構造轉移矩陣 A = [[a%mod, 0], [c%mod, 1]]
3. 計算 Aⁿ (mod mod)
4. xₙ = (Aⁿ[0][0]·x₀ + Aⁿ[1][0]) % mod
5. 輸出 xₙ % g

複雜度分析

• 矩陣乘法：O(2³) = O(1)
• 快速冂：O(log n)
• 總體：O(log n)，完美解決大 n 問題

此題展示了矩陣快速冂在線性遞推加速中的強大威力，結合快速乘處理大數取模，是競賽編程中的經典技巧組合。