분할 정복을 이용한 거듭제곱

문제 풀이 N이 상당히 크기때문에 분할 정복으로 푼다. N이 짝수 일 경우 N / 2와 N / 2 N이 홀수 일 경우 N - 1과 N 행렬을 곱하면서 수가 점점 커지기 때문에 곱하면서 MOD연산이 필요하다. 코드 #include #include #include #define MOD 1000 using namespace std; int N; long long B; map cache; vector matrix; vector mulMatrix(vector m1, vector m2) { vector outMatrix; outMatrix.resize(N); for (int i = 0; i < N; ++i) { outMatrix[i].resize(N); } // m1과 m2 행렬의 곱 for (int i = 0; ..

문제 풀이 일반적인 다이나믹 프로그래밍으로 해결하려고 하면 메모리 초과 위의 식을 이용하여 피보나치 수열을 행렬의 거듭제곱으로 계산할 수 있다. 분할 정복을 이용한 거듭제곱으로 해결한다. 코드 #include #include #include using namespace std; #define MOD 1000000007 map cache; vector matrix = { {1, 1}, {1, 0} }; vector mulMatrix(vector m1, vector m2) { vector outM = { {0, 0}, {0, 0} }; outM[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD; outM[0][1] = (m1[0][0] * m2[0][1]..