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; }