(13976) 타일 채우기 2

https://www.acmicpc.net/problem/13976

단계별로 풀어보기

50단계(동적 계획법 4) 5번째

 

 

 

N이 홀수라면 3N은 홀수이므로 2칸짜리 타일들로 꽉 채울 수 없어서 경우의 수는 자명하게 0이다.

짝수일 때 점화식은 여러 곳에서 유도 방법을 찾아볼 수 있으므로 생략하고 결론만 말하면

A(n)= 4*A(n-2)-A(n-4)이다. 이를 행렬로 나타내면

이렇게 되고, 이를 반복하며 정리하면

이 식을 얻을 수 있다. 직접 구해보면 A(0)=0, A(2)=3이고 행렬 제곱은 분할 정복을 이용하면 O(log N)에 풀 수 있다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define p 1000000007
typedef vector<vector<long>> matrix;

matrix operator*(const matrix &a, const matrix &b){
  matrix res(a.size(), vector<long> (b[0].size()));

  for(int i=0;i<res.size();i++){
    for(int j=0;j<res[0].size();j++){
      for(int k=0;k<a[0].size();k++){
        res[i][j]= (res[i][j]+a[i][k]*b[k][j]+p)%p;
      }
    }
  }

  return res;
}

matrix power(matrix &base, long expo){
  matrix res(base.size(), vector<long> (base.size()));
  
  for(int i=0;i<base.size();i++)  res[i][i]= 1;
  
  while(expo){
    if(expo&1)  res= res*base;
    expo/= 2;
    base= base*base;
  }
  
  return res;
}

int main() {
  long n;
  
  cin >> n;
  
  if(n&1){
    cout << 0;
    
    return 0;
  }
  
  matrix a= {{4, -1}, {1, 0}};
  
  a= power(a, n/2);
  
  cout << (3*a[1][0]+a[1][1])%p;
  
  return 0;
}