백준 1588번 수열

문제 링크

$3^{20}$을 다 계산하면 큰일난다. $solve(n,k)$를 $n$초가 지났을 때 $k$번째 숫자, 그리고 $k$번째까지 $1,2,3$의 개수라고 정의하자. 이는 $solve(n-1,k/3)$을 통해 알아낼 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int S, L, R, N;
 
vector<int> vectors[4] = {{}, {1, 3, 2}, {2, 1, 1}, {2, 3, 2}};
 
vector<int>& getvec(int num) {
    return vectors[num];
}
 
vector<int> solve(int n, int k) {
    // ret[0] -> k번째 숫자
    // ret[1] ~ ret[3] -> n번 진행했을 때 k번째까지 1, 2, 3의 개수
    vector<int> ret(4);
 
    if (n == 0) {
        ret[0] = S;
        ret[S] = 1;
        return ret;
    }
 
    vector<int> tmp = solve(n - 1, k / 3);
    int ln = tmp[0];
    vector<int>& v = getvec(ln);
 
    if (k % 3 == 0) {
        ret[0] = v[0];
        ret[v[0]]++;
        tmp[ln]--;
    }
    else if (k % 3 == 1) {
        ret[0] = v[1];
        ret[v[0]]++;
        ret[v[1]]++;
        tmp[ln]--;
    }
    else {
        ret[0] = v[2];
    }
 
    ret[1] += tmp[1] + tmp[2]*2;
    ret[2] += tmp[1] + tmp[2] + tmp[3]*2;
    ret[3] += tmp[1] + tmp[3];
 
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> S >> L >> R >> N;
 
    vector<int> v1 = solve(N, R);
    vector<int> v2;
    if (L == 0) v2 = {0, 0, 0, 0};
    else v2 = solve(N, L-1);
 
    cout << v1[1] - v2[1] << ' ' << v1[2] - v2[2] << ' ' << v1[3] - v2[3] << '\n';
 
    return 0;
}