[康托展开+逆展开] 理解 和 代码总结

之前 听说过
现在做IDA* 八数码没有一坨优化过不去问题必须学的
这里写下笔记

首先洛谷 P1379
https://www.luogu.org/problem/P1379

我自己对[康托展开+逆展开] 代码总结
n^2 和 logn 我都写了 洛谷这个题强制要优化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int mod = 998244353;
int n, a[maxn], c[maxn], f[maxn];

void add(int x, int y) {
	for(; x <= n; x += (x & -x)) c[x] += y;
}

int sum(int x) {
	int res = 0;
	for(; x; x -= (x & -x)) res += c[x];
	return res;
}

int cantor(int *a, int n) {
	int x = 0;
	for (int i = 1; i <= n; ++i) {
		int tmp = 0;
		for (int j = i + 1; j <= n; ++j)
			if (a[j] < a[i])
				tmp++;
		x += f[n - i] * tmp;
	}
	return x ; // + 1 要不从零开始
}


void decantor(int n, int k, int *a) {
	int j, t, vst[8]= {0};
	--k;
	for (int i =  1; i <= n; i ++) {
		t = k / f[n - i];
		for (j = 1; j <= n; j ++){
			if (!vst[j]) {
				if (t == 0) break;
				-- t;
			}
		}
		a[i] = j;
		vst[j] = 1; 
		k %= f[n - i];
	}
	for(int i = 1; i <= n; i++) cout << a[i] << " " ; cout << endl;
}

int main() {
	cin >> n;
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i ++) f[i] = 1ll * f[i - 1] * i % mod;
	// n * n cantor 函数 
// for(int i = 1; i <= n; i ++) cin >> a[i], add(i, 1);
// ll ans = 0;
// cout << cantor(a, n) << endl;

// nlgn 树状数组优化 算法 
 
// for(int i = 1; i <= n; i ++) {
// ans = (ans + (1ll * (sum(a[i]) - 1) * f[n - i]) % mod) % mod;
// add(a[i], -1);
// }
// cout << ans + 1 << endl;

	// 逆展开 
// int k;
// cin >> k;
// decantor(n, k, a);

	return 0;
}

以下讲解取于教材