거듭제곱2 BOJ13976 타일 채우기 2 BOJ13976 타일 채우기 2 BOJ2133 타일 채우기 같은 문제다. 다만 N의 범위가 다르다. 2133번은 1≤N≤30이기 떄문에 수열의 값을 모두 구해도 된다. 13976번은 1≤N≤1,000,000,000,000,000,000=10^18이기 때문에 행렬의 거듭제곱을 이용하여 풀어야 한다. 필기만 옮기려고 했으나 코드까지 첨부 더보기 #include #include using namespace std; long long DIV = 1000000007; struct Matrix { long long a[2][2]; Matrix() { a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; } Matrix(long long x, long long y, long long z, lo.. 2021. 1. 28. 행렬의 제곱 분할 정복, DP 문제에서 N이 아주 크게 주어지는 경우 자주 이용됨 분할 정복을 이용한 거듭제곱에 있는 문제 거의 다 이런 문제일 것 같다. struct로 행렬을 구현해 곱셈 연산자 오버로딩. 15행에 출력 조건과 수의 범위에 따라 MOD연산 등을 추가한다. 당연하지만 이때 음수 MOD연산도 주의하자,, 통수 맞을 수 있음,, struct Matrix { int size; vector a; Matrix() { size = 0; } Matrix(int n) { size = n; a = vector(n, vector(n)); } Matrix operator *(const Matrix& X) { Matrix RES(size); for (int i = 0; i < size; i++) { for (int j =.. 2021. 1. 16. 이전 1 다음
