BOJ 13976 타일 채우기 2

1 개요

BOJ 13976 타일 채우기 2
2 C++

#include <iostream>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
struct Matrix {
    ll a, b, c, d;
    Matrix operator*(const Matrix& other) const {
        Matrix result;
        result.a = ((a * other.a) % MOD + (b * other.c) % MOD) % MOD;
        result.b = ((a * other.b) % MOD + (b * other.d) % MOD) % MOD;
        result.c = ((c * other.a) % MOD + (d * other.c) % MOD) % MOD;
        result.d = ((c * other.b) % MOD + (d * other.d) % MOD) % MOD;
        return result;
    }
};
ll N;
Matrix base = {4, -1, 1, 0};
Matrix multi = {3, 0, 1, 0};

Matrix power(ll exponent) {
    if (exponent == 1) return base;
    Matrix m = power(exponent / 2);
    if (exponent % 2 == 0) {
        return m * m;
    } else {
        return m * m * base;
    }
}

void solve() {
    if (N % 2 == 1) {
        cout << 0;
        return;
    }
    Matrix m = power(N / 2) * multi;
    cout << (m.c + MOD) % MOD;
}

int main() {
    cin >> N;
    solve();
}