백준 19228번 Key storage

문제 요약

NERC 2019 K번이다. 문제에서 정수의 새로운 해시함수를 제시하는데, 해시 방법은 다음과 같다.

숫자 N이 주어지면, N을 2로 나누고, 나눈 몫을 3으로 나누고, 3으로 나눈 몫을 또 4로 나누고, 몫이 0이 될 때까지 나누는 수를 1씩 늘려가며 나눈다. 그리고 그 과정에서 나온 나머지들의 multiset이 해시값이다. 이를 의사코드로 나타내면 아래와 같다.

function F(N):
    x <- empty multiset
    for(i=2;N>0;++i)
        x.insert(N%i)
        N /= i
    return x

이런 해시 함수가 있을 때, 어떤 숫자 $k$가 들어오면 그것과 같은 해시값을 가지는 자신 이외의 키의 개수를 출력하는 문제이다.

테스트 케이스는 최대 50000개이며, $ 1 \le k \le 10^{18} $이다.

풀이

수의 범위가 매우 넓기 때문에 모든 숫자를 다 해본다거나 그런건 당연히 안된다. 문제에서 요구하는 대로 이 해시 함수는 key와 해시값이 1대1 매칭이 아니다. 일단 해시 함수를 좀 더 간단화 시켜서 생각해보자. 나누는 과정에서 나오는 나머지들의 멀티셋이 아니라, 나오는 나머지들의 순열이라고 생각하자. 이런 해시함수를 $ F' $라고 하자.

$ F(11) = {1,1,2} $이고, $ F'(11) = (1,2,1) $이 된다. 그리고 $ F(15) = {1,1,2} $, $ F'(15) = (1,1,2) $가 된다. 즉, $ F(11)=F(15) $지만 $ F'(11) \ne F'(15) $가 된다. 이런식으로 나온 나머지들의 멀티셋이 아니라 순서를 고정시킨 순열로 생각하면, 이 순열들과 key는 1대1 매칭이 된다. 나온 나머지들을 끝에서부터 차례차례 복원해나가는 방식으로 key를 복원해보면 이를 이해할 수 있다.

다시 원래 함수인 멀티셋으로 돌아오자. 위의 사실로부터 어떤 멀티셋이 있을 때, 그 멀티셋이 나올수 있는 key의 숫자는 해당 멀티셋을 나열하는 방법과 같다는 것을 알 수 있다. $ {1,1,2} $가 주어졌을 때, 나열할 수 있는 방법은 $ (1,1,2),(1,2,1) $ 두 가지밖에 없으며 예제에서 11이 입력으로 주어졌을 때, 답이 1인 것도 확인이 가능하다. 이제 나열할 수 있는 방법을 세보자.

위에서 $ {1,1,2} $가 주어졌을 때, $ (2,1,1) $은 나열할 수 있는 방법에 들어가지 않았다. 왜 그럴까?

나머지들을 나열하는 것이기 때문에 순서대로 (2로 나눈 나머지, 3으로 나눈 나머지, 4로 나눈 나머지)이다. 그렇기 때문에 첫째 자리에는 2가 들어갈 수 없다. 조건 하나를 찾았다.

순서를 정할 때 생각해줘야 할 조건이 하나 더 있는데, 제일 끝자리에 0이 와서는 안된다. 끝자리에 0이 왔다는 것은 나머지가 0이 오고 끝났다는 것인데, 원래 끝나는 조건은 몫이 0이 되는 것이다. 따라서, 0으로 끝나게 되면 몫이 0이고 나머지가 0이라는 소린데 그러면 그 전에 끝났어야 한다. 따라서, 끝자리에 0이 와서는 안된다.

이 두 가지를 염두에 두고 멀티셋을 나열해 나가면 된다. 첫 번째 조건을 생각하면 작은 수가 들어갈 수 있는 곳이 큰 수보다 많다. 따라서, 큰 수부터 배치 해나가면 빠뜨리는 경우 없이 셀 수 있다. 문제에서 주어진 예시를 보자. $ {0,0,0,0,2,3,3,4} $가 주어졌다.

4부터 배치해 나가자. 숫자가 총 8개이므로 사용된 수는 2,3,4,5,6,7,8,9이다. 4가 들어갈 수 있는 곳은 5부터 9까지 다섯 개이다. 4를 하나 넣고 나서 3을 넣어야 하는데 3이 들어갈 수 있는 곳은 4부터 8까지 여섯 개지만, 4가 하나 들어갔으므로 5개 중에 2개를 고르는 것과 같다. 여기까지 계산한 것이 $_5C_1 \times _5C_2 $다. 2가 들어갈 수 있는 곳은 3부터 9까지 7개이며, 이미 3개가 들어갔기 때문에 최종 경우의 수는 $ _5C_1 \times _5C_2 \times _4C_1 =200 $이 된다. 예시와 다르다. 방법이 틀렸을까?

두번째 조건을 빼먹었다. 끝자리에는 0이 와서는 안된다. 그래서 끝에 0이 오는 경우의 수를 빼줘야 한다. 이를 계산 하는 것은 0을 끝자리에 배치했다 치고 $ {0,0,0,2,3,3,4} $를 나열하는 경우의 수를 세주면 된다. 이를 계산하면 72가 나온다.

따라서 $ 200 - 72 - 1 = 127 $로 예제가 잘 나오는 걸 확인했다. 이제 시간복잡도를 계산하자.

주어지는 숫자 $ k $의 범위가 최대 $ 10^{18} $이므로 나올 수 있는 해시값의 크기는 최대 20이다. $ 10^{18} \lt 20! $이기 때문이다. 나열할 수 있는 방법을 계산하는 것도 멀티셋에서 큰 수부터 배치 해나가면 되기때문에 멀티셋의 크기만큼만 걸린다. 따라서 하나의 입력에 대해 답을 계산하는 것은 상수 시간이 걸린다. 이걸로 문제를 풀 수 있다.

다만, 주의할 것이 하나 있는데 끝자리에 0을 배치하고 나열하는 방법의 수를 계산할 때, 아예 배치가 불가능할 수도 있다. {0,2,2,2}가 그 예시다. 이걸 놓쳐가지고 팀연습 돌 때 시간을 너무 낭비했다. 아래는 코드다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
using ll = long long;
vector<ll> f(ll k) {
    vector<ll> ret;
    for (ll i = 2; k > 0; ++i) {
        ret.push_back(k%i);
        k /= i;
    }
    sort(ret.begin(), ret.end(), [](ll a, ll b) {return a > b; });
    return ret;
}

ll cache[25][25];
ll comb(ll n, ll m) {
    if (n == m || m == 0) return 1LL;
    if (n <= 1) return 1LL;
    ll &ret = cache[n][m];
    if (ret != -1) return ret;
    return ret = comb(n - 1, m - 1) + comb(n - 1, m);
}

ll calc(vector<ll> a) {
    ll n = a.size();
    ll chosen = 0;
    ll ret = 1;
    a.push_back(-1);
    for (ll i = 0; i < n; ++i) {
        ll j = i;
        while (j < n && a[j] == a[j + 1]) ++j;
        ll m = j - i + 1;
        ll pos = a[i];
        pos = n - a[i] + 1;
        if (pos >= n) pos = n;
        if (pos - chosen < m) return 0;
        ret *= comb(pos - chosen, m);
        chosen += m;
        i = j;
    }
    return ret;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    ll tc, i; cin >> tc;
    memset(cache, -1, sizeof(cache));
    for (i = 0; i <= 22; i++) { comb(22, i); }
    while (tc--) {
        ll k; cin >> k;
        vector<ll> h = f(k);
        ll ans = calc(h);
        if (h.back() == 0) {
            h.pop_back();
            //cout << calc(h) << '\n';
            ans -= calc(h);
        }
        cout << ans - 1 << '\n';
    }
    return 0;
}