行列累乗法の例題のような素直な問題。

A - Accumulation

解法

行列累乗法 $O(\log T + N)$

疑似コードの最終行

    X=(A*X+B) mod C

は線形な演算なので、\(\left( \begin{matrix} X' \\ 1 \\ \end{matrix} \right) = \left( \begin{matrix} A & B \\ 0 & 1 \\ \end{matrix} \right) \left( \begin{matrix} X \\ 1 \\ \end{matrix} \right) \pmod C\)と書ける。ここで、\(\left( \begin{matrix} X' \\ 1 \\ \end{matrix} \right) = \left( \begin{matrix} A & B \\ 0 & 1 \\ \end{matrix} \right)^T \left( \begin{matrix} X \\ 1 \\ \end{matrix} \right) \pmod C\)とすれば、この演算を$T$回まとめて行うことができる。 この行列の$T$乗を事前に$O(\log T)$で計算しておけばよい。

実装

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
void mul(ll (& dest)[2][2], ll (& a)[2][2], ll (& b)[2][2], ll c) {
    ll t[2][2] = {};
    repeat (y,2) repeat (z,2) repeat (x,2) {
        t[y][x] += a[y][z] * b[z][x] % c;
        t[y][x] %= c;
    }
    repeat (y,2) repeat (x,2) dest[y][x] = t[y][x];
}
int main() {
    int n; cin >> n;
    ll x, t, a, b, c; cin >> x >> t >> a >> b >> c;
    {
        ll e[2][2] = { { a, b }, { 0, 1 } };
        ll f[2][2] = { { 1, 0 }, { 0, 1 } };
        for (int i = 0; (1ll << i) <= t; ++i) {
            if (t & (1ll << i)) mul(f, f, e, c);
            mul(e, e, e, c);
        }
        a = f[0][0];
        b = f[0][1];
    }
    ll s = 0;
    repeat (i,n) {
        s += x;
        x = (a*x%c + b) % c;
    }
    cout << s << endl;
    return 0;
}