콘 토 전개 집합 기초 예제 + 템 플 릿 자세히 설명

단순히 어떻게 쓰 고 어떻게 계산 하 는 지, 남 의 말 을 하 다.
예비 개념: 배열: 하나의 숫자 n 에 대한 배열 은 [1, n] 의 모든 숫자 를 포함 하 는 서열 이다.즉 n 에서 3 을 취하 면 123, 132, 213 을 n 의 배열 이 라 고 하지만 112, 12, 13 등 은 이런 것 이 배열 이 아니다.
콘 토 전개 란 무엇 일 까요?n 의 전체 배열 을 표시 하고 사전 순서에 따라 배열 하 는 것 이다.n. 세 가 지 를 모두 6 가지 로 배열 하면 6 가지 사전 순서 가 작은 순서 로 배열 한다. 예 를 들 어 123 의 번 호 는 1, 132 의 번 호 는 2 이다.
우선 우리 가 제시 한 배열 에 따라 그 가 대표 하 는 번호 가 얼마 인지, 예 를 들 어 서열 2143 의 번 호 를 구 하 는 방법 을 말 해 보 자.그의 구법 은 이 렇 습 니 다. 첫 번 째 숫자 는 2 입 니 다. 우 리 는 아직 사용 하지 않 은 숫자 중 2 가 있 는 위 치 를 알 아야 합 니 다. - 1 의 이 숫자 는 temp 1 로 좋 습 니 다. 현재 사용 하지 않 은 숫자 는 1234 (어 릴 때 부터 큰) 이 고 2 는 두 번 째 로 큰 숫자 입 니 다. 하 나 를 빼 면 temp 1 = 1 입 니 다.그리고 우 리 는 또 다른 숫자 temp 2 가 필요 합 니 다. 이 숫자 는 무엇 입 니까? n 에서 현재 서열 에 있 는 이 숫자 를 뺀 위 치 는 temp 2 = 4 - 1 = 3 입 니 다. temp 2 에 대한 단계 곱 하기 즉 temp 2 = 3 입 니 다! =6;temp 1, temp 2 를 곱 해서 이 곱 한 숫자 에 뒷 자리 수 를 더 한 temp 1 temp 2 (과정 에서 계산 한 숫자 가 바로 이 겁 니 다) 2: temp 1 = 1, temp 2 = 3! =6，temp1 * temp2 = 6； 1: temp 1 = 0 (현재 사용 하지 않 은 숫자 는 1, 3, 4), temp 2 = 2! =2，temp1 * temp2 = 0； 4: temp 1 = 1, (1, 2 를 다 사 용 했 는데 이제 3, 4 가 남 았 습 니 다), temp 2 = 1! = 1, temp 1 temp 2 = 1; 3: temp = 0 (3 만 남 았 습 니 다), temp 2 = 0! = 1; temp 1 * temp 2 = 0;
그러면 2143 이라는 서열 에 대한 번 호 는 6 + 0 + 1 + 0 = 7 이지 만 마지막 에 1 을 더 해서 7 + 1 = 8 로 만 드 는 것 이 정 답 입 니 다. 그의 번 호 는 원래 0 부터 계산 되 었 기 때문에 1234 로 계산 하면 0 입 니 다. 우 리 는 그 에 게 1 부터 계산 하 라 고 했 습 니 다.
코드 구현 에 있어 서 는 트 리 배열 로 접두사 와 어떤 숫자 가 현재 몇 위 에 있 는 지 알 수 있다.
그러면 지금 우 리 는 한 가지 질문 을 하 겠 습 니 다. 번호 와 n 을 알 고 있 습 니 다. 우 리 는 그 가 대표 하 는 서열 이 어떤 서열 인지 어떻게 구 합 니까? 우 리 는 n 이 4 이 고 번호 가 8 이 라 고 가정 합 니 다. 방금 의 예 를 들 어 t 로 8 을 표시 하 는 것 은 이렇게 구 하 는 것 입 니 다. 먼저 번호 - 1 을 구 합 니 다. (우리 위 에 마지막 에 1 을 더 한 것 을 기억 합 니까?). t = 8 - 1 = 7; n 개의 숫자 가 있 습 니 다. 우 리 는 첫 번 째 숫자 부터 계산 합 니 다. i 로 현재 몇 번 째 숫자 를 계산 하고 있 는 지 표시 합 니 다. t 로 (n - i) 의 단 계 를 제거 하여 하나의 숫자 를 얻 습 니 다. 이 숫자 는 사용 하지 않 은 숫자 중에서 몇 번 째 로 되 어 있 는 지 표시 합 니 다. 그러나 우 리 는 하 나 를 더 해 야 합 니 다.(우리 가 위 에서 계산 한 번 호 는 - 1 이 고, 여기 가 바로 거꾸로 구 하 는 것 이 + 1 이라는 것 을 기억 합 니 다.) 지금 이 순위 가 대표 하 는 숫자 는 바로 현재 위치의 숫자 입 니 다. 두 번 더 보면 내 가 밀어 줄 수 없습니다. i = 1 int node = t / (4 - i)! = 7 / 3! = 1; node + 1 = 2; node = 2 를 계산 하면 사용 하지 않 을 숫자 중 두 번 째 가 바로 (1234 안에 두 번 째 가 2) 입 니 다.그러면 첫 번 째 숫자 는 2 입 니 다.! = 1, 현재 사용 하지 않 은 숫자 는 (3, 4), i = 3 int node = t / (4 - i)! = 1 / 1! = 1, node + 1 = 2, 사용 하지 않 은 숫자 중 두 번 째 (현재 사용 하지 않 은 숫자 는 34, 두 번 째 는 4), 업데이트 t, t = t% (4 - i)! = 0; (현재 사용 하지 않 은 숫자 는 3) i = 4 int node = t / (4 - i)! = 0 / 0!(트 리 배열 은 두 개의 log, 선분 트 리 하나의 log) 입 니 다. 낙 곡 p3014 이것 이 바로 순 누 드 콘 토 전개 + 역 전개 예제 입 니 다. 구체 적 인 트 리 배열 이 어떻게 이 루어 지 는 지 에 대해 서 는 별로 말 하지 않 았 습 니 다. 이 편 은 주로 콘 토 가 펼 쳐 졌 기 때 문 입 니 다. 제 코드 에 트 리 배열 부분 에 대해 모 르 는 것 이 있 으 면 메 시 지 를 남 겨 주세요.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include 
#define debug cout<
#define int long long
#define RE register
#define yn yn_
using namespace std;
const long long max_ = 1530000 + 7;
const int mod = 998244353;
const int inf = 1e9;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
int n,value[max_];

int c[100];
int low_bit(int x) {
	return (x&(-x));
}

void change(int x, int value) {
	while (x <= n) {
		c[x] += value;
		c[x] %= mod;
		x = x + low_bit(x);
	}
}

int sum_(int x) {
	// 1 x   
	int ans = 0;
	while (x != 0) {
		ans += c[x];
		ans %= mod;
		x = x - low_bit(x);
	}
	return ans%mod;
}
int erfen(int L, int R, int aim) {
	if (L == R)return L;
	int mid = L + (R - L) / 2;
	if (sum_(mid) >= aim) {
		return erfen(L, mid, aim);
	}
	else
	return erfen(mid + 1, R, aim);
}
signed main() {
	int T;
	n = read(), T = read();
	value[0] = 1;
	for (int i = 1; i <= 20; i++) {
		value[i] = value[i - 1]  * i;
	}
	while (T--){
		char ch;
		cin >> ch;
		if (ch == 'P') {
			//     
			memset(c, 0, sizeof(c));
			for (int i = 1; i <= n; i++)
				change(i, 1);
			int temp = read(); temp--;
			for (int i = 1,num = n - 1; i <= n;num--, i++) {
				int aim = temp / value[num] + 1; temp %= value[num];
				int t = erfen(1, n, aim);
				cout << t << " ";
				change(t, -1);
			}
			cout << "
";
		}
		else {//    
			memset(c, 0, sizeof(c));
			for(int i =1; i <= n ; i++)
				change(i, 1);
			int ans = 1;//  1  
			for (int i = 1, jiecheng = n - 1; i <= n; jiecheng--, i++) {
				int temp = read();
				ans += value[jiecheng] * sum_(temp - 1);
				change(temp, -1);
			}
			cout << ans << "
";
		}
	}
	return 0;
}