2x2行列の掛け算とpow

Quiz

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

Submit

https://yukicoder.me/submissions/341945

解法

公式解説の通り

行列ライブラリ

• 持ってない・・・。とりあえず必要な掛け算とpowを書いた
• 2x2限定

using ll = long long;
using VV = vector<vector<ll> >;

VV mul(VV A, VV B){
    VV C = {{0, 0}, {0, 0}};
    C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % mod;
    C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % mod;
    C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod;
    C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % mod;
    return C;
}

VV pow(VV A, ll N){
    if(N==1){
        return A;
    }

    if(N%2==0){
        return pow(mul(A, A), N/2);
    }
    else{
        return mul(A, pow(A, N-1));
    }
}