Powerful Sum [Kodamanと愉快な仲間たち T]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/powerful-sum

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/powerful-sum/submissions/code/1316487336

Nがとても大きいので、普通に計算するんじゃないんだろうなと言うのはわかる。 10¹⁸ということは数学一本で計算できるか、logNかどちらかである。 とりあえず、対称式でググりまくると、こういうサイトが出てくる。 これによると、An = x^n + y^nとすると、An = (x+y)An-1 - xyAn-2である。 漸化式が作れれば、行列累乗で答えも作れる。

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

    Vec v(3, 0);
    v[0] = (A + mod) % mod;
    v[1] = 2;
    v[2] = 0;

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

    m[1][0] = 1;
    m[1][1] = 0;
    m[1][2] = 0;

    m[2][0] = 1;
    m[2][1] = 0;
    m[2][2] = 1;

    m = fastpow(m, N - 1);
    v = mulMatVec(m, v);
    int ans = (v[0] + v[2]) % mod;
    
    cout << ans << endl;
}