【題解】CSES 1722 Fibonacci Numbers

#include <iostream>
using namespace std;
 
long long n, m[2][2], ans[2][2], p = 1e9+7;
 
int main() {
    cin >> n;
    m[0][0] = 1;
    m[0][1] = 1;
    m[1][0] = 1;
    ans[0][0] = 1;
    while (n){
        if (n&1){
            long long tmp[2][2] = {};
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 2; j++){
                    for (int k = 0; k < 2; k++){
                        tmp[i][j] += m[i][k] * ans[k][j];
                        tmp[i][j] %= p;
                    }
                }
            }
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 2; j++){
                    ans[i][j] = tmp[i][j];
                }
            }
        }
        n >>= 1;
        long long tmp[2][2] = {};
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                for (int k = 0; k < 2; k++){
                    tmp[i][j] += m[i][k] * m[k][j];
                    tmp[i][j] %= p;
                }
            }
        }
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                m[i][j] = tmp[i][j];
            }
        }
    }
    cout << ans[1][0] << "\n";
}