hckim

문제링크

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

문제해석

• 일직선 정수 좌표상에 타로집 - 당근 - 하나코집 이 순서대로 있다.
• 오징어는 한번 이동할 때 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) 라고하고 표를 만들면 다음과 같다

• 각 열에서 시작하는 대각선에 있는 수들은 오른쪽 대각선에 포함되어 있을 수록 단조롭게 크다는 것을 관찰할 수 있고
• 각 대각선 안에서의 순서는 맨위 수부터 두 칸씩 건너 뛰는 순서로 되어 있다는 것을 관찰 할 수 있다(홀수 칸에서 조금 수정해야함)
• 따라서 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';
}

문제링크

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

풀이

1. $f(x)$: x 이하의 제곱 ㄴㄴ 수 개수
2. $f(t) = K$ 인 제일 작은 t 가 답이고 parametric search 로 찾는다.
3. $f(t)$ 구현
   1. $t - $ ($\sqrt{t}$ 이하의 소수들의 조합으로 구성된 수들의 제곱의 합집합 개수)
   2. 포함배제의 원리로 홀수종류 포함은 더하기, 짝수종류 포함은 빼기

코드

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  vector<long long> prime;
  vector<int> isPrime(sqrt(2e9) + 1, true);
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i * i < isPrime.size(); ++i) {
    if (!isPrime[i]) continue;
    for (int j = i * i; j < isPrime.size(); j += i) {
      isPrime[j] = false;
    }
  }
  for (int i = 2; i < isPrime.size(); ++i) {
    if (isPrime[i]) prime.push_back(i);
  }

  // 1 이상 x 이하 제곱 ㄴㄴ 수 개수
  auto getNum = [&](long long x) {
    // cnt, idx, num
    queue<tuple<int, int, long long> > q;
    for (int i = 0; i < prime.size(); ++i) {
      auto e = prime[i];
      if (e * e > x) break;
      q.push({1, i, e});
    }

    long long ret = 0;
    map<int, int> visited;
    while (q.size()) {
      auto [fcnt, fidx, fn] = q.front();
      q.pop();

      ret += (fcnt & 1 ? 1LL : -1LL) * (x / (fn * fn));

      for (int i = fidx + 1; i < prime.size(); ++i) {
        auto e = prime[i];
        if (fn * e * fn * e > x) break;
        if (fn % e == 0) continue;
        q.push({fcnt + 1, i, fn * e});
      }
    }
    return x - ret;
  };

  long long lo = 0;
  long long hi = 2e9;

  long long K;
  cin >> K;
  while (lo + 1 < hi) {
    long long mid = (lo + hi) >> 1;
    if (getNum(mid) < K) lo = mid;
    else hi = mid;
  }
  cout << hi << '\n';
}

문제 링크

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

풀이 1. Hashing, Rabin-Karp algorithm, Parametric search

• 길이 $l$ 인 부분 문자열이 전체 문자열내에서 두번 이상 등장한다고 하자
• 그 부분 문자열의 부분 문자열들(길이 $1, 2, ..., l$) 또한 전체 문자열내에서 두번 이상 등장한다
• 따라서 결정문제: 길이 $l$ 부분문자열이 2번이상 등장하는가? 에 대한 답의 분포는 이분적이다($T, ..., T, F, F, ..., F$)
• 각 결정문제를 해결할 때에는 라빈카프 알고리즘의 롤링해쉬함수를 이용한다

코드 1.

• 시간복잡도: $O(LlogL)$
  • Parametric search: $O(logL)$
  • 결정문제: $O(L)$

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int L;
    cin >> L;
    string s;
    cin >> s;

    long long MOD = 1e5 + 3;
    long long MUL = 2;

    auto check = [&](int l) {
        vector<vector<int> > hashTable(MOD);
        long long h = 0;
        long long MUL_POW_L = 1;
        for (int i = 0; i < l; ++i) {
            h *= MUL;
            h += s[i] - 'a' + 1;
            h %= MOD;
            MUL_POW_L *= MUL;
            MUL_POW_L %= MOD;
        }
        hashTable[h].push_back(0);

        for (int i = 1; i + l - 1 < L; ++i) {
            h *= MUL;
            h %= MOD;
            h -= (1LL * (s[i - 1] - 'a' + 1) * MUL_POW_L) % MOD;
            h += s[i + l - 1] - 'a' + 1; 
            h %= MOD;
            if (h < 0) h += MOD;

            for (auto idx: hashTable[h]) {
                if (s.compare(i, l, s, idx, l) == 0) return true;
            }
            hashTable[h].push_back(i);
        }
        return false;
    };

    int lo = 0;
    int hi = L;

    while (lo + 1 < hi) {
        int mid = lo + hi >> 1;
        if (check(mid)) lo = mid;
        else hi = mid;
    }

    cout << lo << '\n';
}

풀이 2. Suffix array and LCP array

• $*max\_element(all(lcp)) = lcp[i]$ 일 때
  • 반복 문자열 최대길이 $= lcp[i]$
  • 반복 문자열 $= s[sa[i]:sa[i] + lcp[i] - 1]$

코드 2.

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int L;
    cin >> L;
    string s;
    cin >> s;

    auto buildSA = [&](string& s) {
        int N = s.size();
        vector<int> sa(N), r(2 * N), nr(2 * N);
        for (int i = 0; i < N; ++i) {
            sa[i] = i;
            r[i] = s[i];
        }
        for (int d = 1; d < N; d <<= 1) {
            auto cmp = [&](int i, int j) {
                return r[i] < r[j] || (r[i] == r[j] && r[i + d] < r[j + d]);
            };
            sort(all(sa), cmp);
            for (int i = 1; i < N; ++i) {
                nr[sa[i]] = nr[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
            }
            r = nr;
        }
        return sa;
    };

    auto buildLCP = [&](string& s) {
        int N = s.size();
        auto sa = buildSA(s);
        vector<int> lcp(N), isa(N);
        for (int i = 0; i < N; ++i) {
            isa[sa[i]] = i;
        }
        for(int k = 0, i = 0;i < N;++i) {
            if(isa[i]){
                for(int j = sa[isa[i]-1]; max(i, j) + k < N && s[i+k] == s[j+k]; ++k);
                lcp[isa[i]] = (k ? k-- : 0);
            }
        }
        return lcp;
    };

    auto lcp = buildLCP(s);
    cout << *max_element(all(lcp)) << '\n';
}