[ICPC] 백준 9341 - ZZ

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

조건 정리

일단 문제를 편하게 풀기 위해 ZZ(0, 0)을 정의할 필요가 있다.

 

$ZZ(0, 0) = b - a$로 둔다.(피보나치수열을 생각한다.)

직접 해보기

10 * 10 테이블을 단순한 dp로 출력해보자.

 

 

그러면 다음 발견을 할 수 있다.

 

 

어떤 항은 위처럼 Z 모양으로 더한 결과와 같다.

 

수식으로 나타내면 다음과 같다.

 

$ZZ(a, b) = [\sum\limits_{i = 0}^{a}ZZ(i, b - 1)] + ZZ(0, b - 2)$

 

그러면 우리는 위 식의 전개를 행렬로 표현할 수 있다. 예를 들어 c가 2인 경우 아래처럼 된다.

 

$\left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{matrix} \right] \left[ \begin{matrix} ZZ(0, i - 2) \\ ZZ(0, i - 1) \\ ZZ(1, i - 1) \\ ZZ(2, i - 1) \end{matrix} \right] = \left[ \begin{matrix} ZZ(0, i - 1) \\ ZZ(0, i) \\ ZZ(1, i) \\ ZZ(2, i) \end{matrix} \right]$

 

행렬 곱셈식을 다 구했으니 남은건 행렬 거듭제곱으로 원하는 해를 구하면 된다.

 

좌항에 들어가는 초기 열벡터의 경우 처음부터 시작하므로 b - a, a, a, a,..., a로 채워주면 된다.

 

전체 코드 - d가 1이거나 2일 경우는 따로 계산했다.

#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+9;
using MATRIX = vector<vector<ll>>;
MATRIX mt;
 
MATRIX operator * (const vector<vector<ll>> &l, const vector<vector<ll>>& 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 < a; k++)
      {
        ret[i][j] += l[i][k] * r[k][j];
        ret[i][j] %= mod;
      }
    }
  }
  return ret;
}
 
MATRIX mat_power(vector<vector<ll>> mat, int a)
{
  if (a == 1) return mat;
  if (a & 1) return mat_power(mat, a - 1) * mat;
  return mat_power(mat * mat, a / 2);
}
 
int t;
int a, b, c, d;
 
MATRIX get_rhs(int to)
{
  MATRIX ret;
  ret.push_back({b - a});
  for (int i = 1; i <= to; i++) ret.push_back({a});
  return ret;
}
 
void solve()
{
  cin >> t;
  while (t--)
  {
    cin >> a >> b >> c >> d;
    if (d == 1)
    {
      cout << a << '\n';
      continue;
    }
    else if (d == 2)
    {
      cout << (b + c * a) % mod << '\n';
      continue;
    }
 
    mt = MATRIX(c + 2, vector<ll>(c + 2));
    for (int i = 0; i < c + 2; i++)
    {
      for (int j = 0; j <= i; j++)
      {
        mt[i][j] = 1;
      }
    }
    swap(mt[0][0], mt[0][1]);
    auto pm = mat_power(mt, d - 1);
    auto rhs = get_rhs(c + 1);
    auto result = pm * rhs;
    cout << result.back().back() << '\n';
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

보너스

이렇게 행렬 거듭제곱으로 푸는 동적계획법 문제는 벌레캠프 메시 알고리즘으로 풀 수 있다고 알려진다.

 

관심 있으면 구사과 블로그를 참고해보자.