백준 18287 - 체스판 이동

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

규칙 살펴보기

홀수 행와 짝수 행일 때의 이동은 그림으로 나타내면 다음과 같다.

 

 

문제에 아래로 가는 것만 가능하다 했으므로 다른 이동은 무시한다.

 

그러면 우리는 이 이동을 표현한 전이 행렬을 구상할 수 있다.

 

MATRIX[i][j] := 현재 행의 i열에서 다음 행의 j열로 가는 경우의 수

 

그러면 $M^{2}$ 크기의 전이 행렬 두 개를 만들 수 있다.

이동 합성

행렬을 만든 건 좋은데 이 따로국밥인 행렬들을 어떻게 처리할지 난감하다.

 

이럴 때는 그냥 홀수 행 전이 행렬과 짝수 행 전이 행렬을 곱해 2번 이동하는 행렬을 만들면 된다.

 

그러면 우리는 2칸씩 이동하는 행렬을 표현했으므로 남은건 행렬 거듭제곱을 통해 이동 횟수 계산을 $O(M^{3} \log N)$의 시간 복잡도로 계산할 수 있다.

 

이동 횟수 1이 나머지로 있을 수 있는데 그러면 홀수 행 이동 행렬을 한 번 곱해주면 끝난다.

 

위의 사항과 시작 행이 1이라는 것을 유의하며 코드를 짜면 정답을 받을 수 있다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
const int mod = 1e9+7;
using MATRIX = vector<vector<ll>>;
MATRIX mt;
 
MATRIX operator * (const MATRIX &l, const MATRIX &r)
{
  int a = l.size();
  int b = r[0].size();
  MATRIX ret(a, vector<ll>(b));
 
  for (int i = 0; i < a; i++)
  {
    for (int j = 0; j < b; j++)
    {
      for (int k = 0; k < l[0].size(); k++)
      {
        ret[i][j] += l[i][k] * r[k][j];
        ret[i][j] %= mod;
      }
    }
  }
  return ret;
}
 
MATRIX mat_power(MATRIX mat, int a)
{
  if (!a)
  {
    MATRIX ret(mat.size(), vector<ll>(mat.size()));
    for (int i = 0; i < mat.size(); i++)
    {
      ret[i][i] = 1;
    }
    return ret;
  }
  if (a == 1) return mat;
  if (a & 1) return mat_power(mat, a - 1) * mat;
  return mat_power(mat * mat, a / 2);
}
 
int n, m;
 
void solve()
{
  cin >> n >> m;
  --n;
  MATRIX parity_odd(m, vector<ll>(m));
  MATRIX parity_even = parity_odd;
 
  if (!n)
  {
    cout << m;
    return;
  }
 
  for (int i = 0; i < m; i++)
  {
    int left = i - 1;
    int right = i + 1;
    if (left >= 0)
    {
      parity_odd[i][left] = 1;
      parity_even[i][left] = 1;
    }
    if (right < m)
    {
      parity_odd[i][right] = 1;
      parity_even[i][right] = 1;
    }
    parity_even[i][i] = 1;
  }
 
  MATRIX two_mv = parity_odd * parity_even;
 
  auto presult = mat_power(two_mv, n / 2);
  int one_more = (n & 1) > 0;
  if (one_more) presult = presult * parity_odd;
 
  ll ans = 0;
  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j < m; j++)
    {
      ans += presult[i][j];
      ans %= mod;
    }
  }
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록