rot and rot [OyamaC]

https://www.hackerrank.com/contests/oyamac/challenges/rot-and-rot

前提知識

• 行列累乗

解説

https://www.hackerrank.com/contests/oyamac/challenges/rot-and-rot/submissions/code/1321979239

今回の操作はxにコマがあるとすると、A(A+1)x+Bによって次のコマの場所がわかる。
この操作をN回行うと答え。

このような線形漸化式は行列累乗によって高速に計算可能であることが知られている。
以下のように行列とベクタを作って計算していこう。

行列m  
| A+1 B |  
| 0   1 |  
  
ベクタv  
| S |  
| 1 |  

答えはm^Nvとなる。

int S, A, B, N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> A >> B >> N;

    Mat m(2, Vec(2, 0));
    m[0][0] = A + 1;
    m[0][1] = B;
    m[1][0] = 0;
    m[1][1] = 1;

    Vec v(2, 0);
    v[0] = S;
    v[1] = 1;

    m = fastpow(m, N);
    v = mulMatVec(m, v);

    cout << v[0] << endl;
}