はまやんはまやんはまやん

hamayanhamayan's blog

隣接3項間の漸化式 [yukicoder 891]

https://yukicoder.me/problems/no/891

前提知識

解説

https://yukicoder.me/submissions/382008

問題を見るとフィボナッチ数の定義に似ている。
ある項のフィボナッチ数を高速に求める方法として、行列累乗が知られている。
今回の問題もこれで解ける。

int a, b, n;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> a >> b >> n;

    Mat m(2, Vec(2, 0));
    m[0][0] = 0;
    m[0][1] = 1;
    m[1][0] = b;
    m[1][1] = a;

    m = fastpow(m, n);

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

    v = mulMatVec(m, v);
    cout << v[0] << endl;
}