[ZJOJ] 5772 [NOIP 2008 시 뮬 레이 션] 오늘 AK 했 어 요?

Description
AK: All kill "당신 은 왜 책 을 외우 지 않 았 습 니까?" "아니요, 저 는 그냥 책 을 외우 지 않 았 습 니 다." "................................................: 하나, 둘, 셋, 하나, 둘, 둘, 셋, 셋, 하나, 둘, 셋, 둘, 둘, 셋.그 는 사전 서열 k 작은 n 의 배열 이 무엇 인지 알 고 싶 어 합 니까?인 플 리 킹 이 책 을 외 우 러 잡 혀 갔 기 때문에 이 문 제 는 만인 에 게 경 배 를 받 는 다 라 오 씨 에 게 맡 길 수 밖 에 없습니다.
Input
한 줄, 두 개의 수, 각각 n, k 이다.n, k 의 의 미 는 제목 설명 참조.
Output
한 줄, n 개의 수.사전 순서 k 작은 n 의 배열 을 대표 합 니 다.두 수 사 이 를 빈 칸 으로 구분 하 는 것 을 주의해 라.
Sample Input
Sample Input1：
1 1
Sample Input2：
2 2
Sample Output
Sample Output1：
1
Sample Output2：
2 1
Data Constraint
【 데이터 약 정 】 10% 의 데이터 에 대하 여: 1 < = n < = 3 대 20% 의 데이터, 1 < = n < = 9 대 30% 의 데이터: 1 < = n < = 18, 1 < = k < = 10 ^ 6 대 60% 의 데이터: 1 < = n < = 18 대 80% 의 데이터: 1 < = n < = 100, 1 < = k < = 10 ^ 100 대 90% 의 데이터: 1 < = n < = 1000, 1 < = k < = 10 ^ 1000 대 100% 의 데이터: 1 < = n < = 100000, 1 = k < = min (10 ^ 20000, n!)
사고의 방향 을 분석 하 다.
토 할 힘 이 없다.징 그 럽 게 하고 싶 으 면 성 공 했 어.
관례 에 따라 우 리 는 데이터 프로 그래 밍 을 한다.
제 1 단
10% 의 데이터: 1 < = n < = 3 계산 + 타 표 예상 점수: 10
제2 단
30% 의 데이터: 1 < = n < = 18, 1 < = k < = 10 ^ 6 계산 + 타 표 는 직접 폭력 적 으로 재 귀 할 수 있 습 니 다.예상 점수: 20 ~ 30
제3 단
60% 의 데이터: 1 < = n < = 18 고급 으로 보 이 는 서양 놀 이 를 콘 토 라 고 부 르 는 것 을 들 어 볼 까요?이 문 제 는 역 강 토 전개 라 고 들 었 습 니 다.관심 없습니다.
제 생각 을 말씀 드 리 겠 습 니 다. 출력 사전 순서 이기 때문에 모든 상황 을 열거 해 보 겠 습 니 다. 46 이라는 데 이 터 를 예 로 들 면...
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 ……..
규칙 을 찾 을 수 있 습 니 다. 첫 번 째 자 리 는 현재 1 ~ 4 에서 사용 하지 않 은 k / 6 큰 숫자 입 니 다. 두 번 째 자 리 는 현재 1 ~ 4 에서 사용 하지 않 은 k / 2 큰 숫자 입 니 다.
6 = 3！ 2 = 2！ 자, 코드 를 쓰 세 요.

#include
#include
#include
using namespace std;

const long long sum[25] = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000};

long long n,k;
bool vis[25];

inline void find_kth(long long x) {
    long long res = 0;
    long long i;
    for(i = 1;i <= n;i++) {
        if(!vis[i]) res++;
        if(res == x) break;
    }
    printf("%lld ",i);
    vis[i] = 1;
}

int main() {
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    long long now,tmp,cnt,x;
    now = k;
    cnt = n;
    while(cnt--) {
        tmp = now / sum[cnt];
        x = now;
        now = now % sum[cnt];
        if(!now) now = sum[cnt];
        if(tmp * sum[cnt] < x) tmp++;
        find_kth(tmp);
    }
    return 0;
}

제4 단
90% 의 데이터 에 대해: 1 < = n < = 1000, 1 < = k < = 10 ^ 1000 고정 밀 은 매번 의 상이 n 보다 작 다 는 것 을 설명 하지 않 기 때문에 이분 상 은 고정 밀 감법, 고정 밀 곱셈 과 관련 되 어 있어 싸움 을 잘 하 는 편 이다.한 번 의 복잡 도 는 O (n log n) 총 복잡 도 O (n ^ 2 log n) 예상 점수: 70 ~ 90
제5 단
100% 의 데이터 에 대하 여: 1 < = n < = 100000, 1 < = k < = min (10 ^ 20000, n!) 이하 작가 의 문제 풀이 에서 인용 합 니 다.
k < = 10 ^ 20000 제 가 책임 지고 말씀 드릴 게 요: 6100! >10 ^ 20000, 하지만 우리 n 은 10 ^ 5 만큼 크다.이것 은 무엇 을 설명 합 니까?이 는 앞의 100000 - 6100 = 93900 개 수 는 반드시 1, 2, 3,..., 93900 (발 견 했 습 니까?) 이 므 로 O (6100 ^ 2) 의 복잡 도 만 이 부분 을 완성 해 야 한 다 는 것 을 의미한다.데이터 구조 나 블록 을 나 눌 줄 모 르 더 라 도 이 문 제 를 해결 할 수 있 습 니 다!
가짜 데이터 범위 예상 점수: 90 ~ 100 (상수 최적화 필요)
총결산
시험장 에 서 는 시간 이 넉넉 하지 않 으 면 고 정 된 글 을 쓰 지 마라.