백준 22581번: IkaNumber

문제링크

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

22581번: IkaNumber

문제해석

• 일직선 정수 좌표상에 타로집 - 당근 - 하나코집 이 순서대로 있다.
• 오징어는 한번 이동할 때 x 좌표에서 x+1 로 가거나 x+2 로 이동할 수 있다
• 오징어가 타로집에서 출발해서 하나코집으로 가는데 중간에 당근을 거치지 않는 경우의 수를 오징어 수
• 가능한 모든 타로집-당근-하나코집 배치에 대하여 unique 한 오징어 수들에서 K 번째로 작은 오징어 수 % MOD 구하기( 1 <= K <= 1e18, MOD = 1e9 + 7)

풀이

• 당근을 거치지 않고 가는 방법은 타로집~당근직전, 2점프, 당근직후~하나코집 이다.
• 타로집~당근직전 과 당근직후~하나코집 각 경우의 수를 곱해서 구할 수 있는데 각각 피보나치 수열임을 알 수 있다.(첫 두항이 1, 2 인)
• 따라서 문제는 모든 피보나치 수열 두개의 곱 중에서 K 번째 값을 찾는 것과 같다.
• v[i][j] = fib(i) * fib(j) 라고하고 표를 만들면 다음과 같다

v[i][j]

• 각 열에서 시작하는 대각선에 있는 수들은 오른쪽 대각선에 포함되어 있을 수록 단조롭게 크다는 것을 관찰할 수 있고
• 각 대각선 안에서의 순서는 맨위 수부터 두 칸씩 건너 뛰는 순서로 되어 있다는 것을 관찰 할 수 있다(홀수 칸에서 조금 수정해야함)
• 따라서 parametric search 로 어떤 열의 대각선에 K 번째 수가 포함되어있는지 찾고 그 대각선 안에서 K 번째 수가 있는 인덱스 i, j 를 찾을 수 있다.
• K 가 크기 때문에 v[i][j] 를 계산할 때 행렬 거듭제곱 이용해서 값을 구해준다

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define MOD 1000000007

vector<vector<long long> > operator*(vector<vector<long long> > v1, vector<vector<long long> > v2) {
    vector<vector<long long> > ret(v1.size(), vector<long long> (v2[0].size(), 0));
    for (long long i = 0; i < ret.size(); ++i) {
        for (long long j = 0; j < ret[0].size(); ++j) {
            for (long long k = 0; k < v1[0].size(); ++k) {
                ret[i][j] = (ret[i][j] + v1[i][k] * v2[k][j]) % MOD;
            }
        }
    }
    return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  freopen("../input.txt", "r", stdin);
  freopen("../output.txt", "w", stdout);

  long long K;
  cin >> K;
  auto fib = [&](long long n) {
    if (n == 0) return 0LL;
    --n;
    vector<vector<long long> > ret = {{1, 0}, {0, 1}};
    vector<vector<long long> > mul = {{1, 1}, {1, 0}};
    while (n) {
        if (n & 1) {
            ret = ret * mul;
        }
        mul = mul * mul;
        n >>= 1;
    }
    return ret[0][0];
  };

  // i 열 대각선 까지 누적개수
  auto f = [&](long long i) {
    if (i & 1) return ((i/2) + 1) * ((i/2) + 1);
    else return (i/2) * ((i/2) + 1);
  };

  // 무슨 열 인지 찾기
  long long lo = 0;
  long long hi = 3e9;
  while (lo + 1 < hi) {
    long long mid = lo + hi >> 1;
    if (f(mid) < K) lo = mid;
    else hi = mid;
  }
  long long idx = hi;
  auto prevNum = f(idx - 1);
  long long partOrder = K - prevNum;
  long long r = 1;
  long long c = idx;

  if (idx % 2 == 0) {
    r += 2 * (partOrder - 1);
    c -= 2 * (partOrder - 1);
  } else {
    r += 2 * (partOrder - 1);
    c -= 2 * (partOrder - 1);
    if (r > c) {
      r -= 1;
      c += 1;
    }
  }

  cout << fib(r + 1) * fib(c + 1) % MOD << '\n';
}