문제 링크 http://icpc.me/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 풀이 dp와 분할 정복을 이용하여 풀이할 수 있다. 분할 정복을 이용한 행렬의 빠른 거듭제곱은 곱셈을 풀면서 공부하자. dp점화식은 dp[n] = 3*dp[n-2] + sum(dp[k]) (k는 n-4부터 0까지 k-=2) 위의 식에 n-2를 대입한식과 위의 식을 빼면 dp[n] = 4 * dp[n-2] - dp[n-4]가 나온다. 행렬식으로 표현하면 위와 같이 표현할 수 있다. 이제 위의 행렬식을 분할정복을 이용하여 빠르게 계산하면 된다. 코드 #include #include using namespace st..