"BOJ 13976 타일 채우기 2"의 두 판 사이의 차이

2024년 2월 2일 (금) 17:30 기준 최신판

1 개요[ | ]

BOJ 13976 타일 채우기 2

2 같이 보기[ | ]

3 C++[ | ]

#include <iostream>
using namespace std;

typedef long long ll;
ll N;
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;
    }
};
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();
}

@@ 5번째 줄: / 5번째 줄: @@
 |분류2= 다이나믹 프로그래밍
 |분류3= 분할 정복을 이용한 거듭제곱
+}}
+==같이 보기==
+{{z컬럼3|
+* [[BOJ 2133 타일 채우기]]
+* [[BOJ 2718 타일 채우기]]
+* [[BOJ 13976 타일 채우기 2]]
+* [[BOJ 14852 타일 채우기 3]]
+* [[BOJ 15700 타일 채우기 4]]
 }}
@@ 13번째 줄: / 22번째 줄: @@
 typedef long long ll;
-const ll MOD = 1000000007;
+ll N;
+ll MOD = 1000000007;
 struct Matrix {
      ll a, b, c, d;
@@ 25번째 줄: / 35번째 줄: @@
      }
 };
-ll N;
 Matrix base = {4, -1, 1, 0};
 Matrix multi = {3, 0, 1, 0};