5431 책 쌓기

a[i] 앞으로 돌린 후 n번째 위치까지 올리는데 걸리는 횟수를 d[n]이라 하자. ( d[0] = 1 )

a1 a2 a3 a4 a5 가 있을 때 a6가 a4,a5 사이에 있어야 한다면 ( d[4] )

a6을 먼저 맨 앞으로 올린 후 a1을 올리고, a2를 다시 a1,a6 사이로 넣어야 한다. ( a1 -> d[0] )

a2를 a1,a6 사이로 올린 다음에는 a3를 맨 위로 올리고 다시 a3을 a2,a6 사이로 넣어야 한다. ( a2 -> d[1] )

그런식으로 계산해보면

a1 -> d[0]

a2 -> d[1] = a2->d[0] + a1->d[0]

a3 -> d[2] = a3->d[0] + a1->d[0] + a2->d[1]

a4 -> d[3] = a4->d[0] + a1->d[0] + a2->d[1] + a3->d[2]

d[4] = a6->d[0] + a1->d[0] + a2->d[1] + a3->d[2] + a4->d[3]

가 되고

이 된다.

이걸로 끝이 아니라 같은 원소가 여러개 있을 때를 생각해봐야 한다.

결론부터 말하자면 같은게 k개 있는 원소가 있으면 (k+1)/2^k 를 곱해주면 된다.

같은게 k개 있는 원소가 m개라면 ((k+1)/2^k)^m 을 곱해주면 된다.

#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
 
typedef long long ll;
 
ll p[51];
 
int main() {
    int t;
    p[0] = 1;
    for (int i = 1; i < 51; ++i) p[i] = p[i - 1] * 2;
    scanf("%d", &t);
    while (t--) {
        int n, a[51], k;
        ll ans = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
            int j = 0, cnt[50] = { 0, }, c[1001] = { 0, };
            if (i&&a[i] >= a[i - 1]) continue;
            for (; j < i && a[i] > a[j]; ++j) {
                cnt[c[a[j]]]--;
                cnt[++c[a[j]]]++;
            }
            if (j == i) 
                continue;
            ll temp = p[j];
            for (k = 2; k < i + 1; ++k) {
                temp /= pow(p[k], (ll)cnt[k]);
                temp *= pow(ll(k + 1), (ll)cnt[k]);
            }
            ans += temp;
            sort(a, a + i + 1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}