### 康拓展开和逆康拓展开
#### 一、康拓展开简介
康拓展开是一种将排列映射到自然数的方法，在ACM算法中有着广泛的应用，尤其是在处理与排列组合相关的题目时非常有用。其核心思想是利用阶乘的概念来唯一地表示一个排列。
#### 二、康拓展开原理
假设我们有一个包含`n`个不同数字的集合{1, 2, ..., n}，那么这`n`个数字的所有可能排列共有`n!`种。康拓展开提供了一种方法，可以将这`n!`种不同的排列映射成从0到`n! - 1`的整数，且这种映射是双射的——也就是说，每一种排列对应唯一的整数，并且任意两个不同的排列对应的整数也不同。
具体的计算公式为：
\[ X = a[n] \cdot (n-1)! + a[n-1] \cdot (n-2)! + ... + a[i] \cdot (i-1)! + ... + a[1] \cdot 0! \]
其中，`a[i]`代表了在当前位置上尚未出现的元素中，当前元素是第几个（从0开始计数）。
#### 三、康拓展开示例
假设我们需要计算排列`34152`的康拓展开值，我们可以按照以下步骤进行：
1. **初始化**：首先定义一个阶乘数组`factory[]`，用于存储0!至9!的阶乘值。
2. **遍历排列**：从左到右遍历排列中的每个元素。
3. **计算贡献值**：对于每一个元素`str[i]`，计算有多少个比它小的元素位于其右侧，即有多少个`str[j] < str[i]`（其中`j > i`）。这个数目乘以`(n-i-1)!`，累加到结果中。
4. **重复步骤3**，直到所有元素都被考虑过。
5. **返回结果**：返回最终的累加结果。
例如，对于`34152`，其康拓展开值为：
- 比`3`小的有`2`个（`1`和`2`），因此`2 * 4! = 48`
- 比`4`小的有`2`个（`1`和`3`），因此`2 * 3! = 12`
- 比`1`小的有`0`个，因此`0 * 2! = 0`
- 比`5`小的有`2`个（`2`和`4`），因此`2 * 1! = 2`
- 比`2`小的有`1`个（`1`），因此`1 * 0! = 1`
最终的康拓展开值为`48 + 12 + 0 + 2 + 1 = 63`。
#### 四、逆康拓展开
逆康拓展开是从一个整数映射回对应的排列的过程。这个过程相对简单，主要思路是通过整除和取余操作逐步确定排列中的各个元素。
具体步骤如下：
1. **初始化**：同样定义一个阶乘数组`factory[]`，并创建一个包含`n`个不同数字的数组`v[]`。
2. **从大到小遍历阶乘数组**：每次用目标整数`x`除以当前阶乘值`factory[i]`，得到的商表示在当前位置应选择的元素，余数则更新为新的目标整数。
3. **更新排列**：根据得到的索引`t`，将数组`v[]`中相应位置的元素加入到结果数组`a[]`中，并从`v[]`中删除该元素。
4. **重复步骤2-3**，直至所有元素都被确定。
例如，已知康拓展开值为`63`，我们希望找到对应的排列`34152`：
1. `63 / 4! = 2... 13`，`a[5] = 2`，因此首位为`3`。
2. `13 / 3! = 2... 1`，`a[4] = 2`，因此第二位为`4`。
3. `1 / 2! = 0... 1`，`a[3] = 0`，因此第三位为`1`。
4. `1 / 1! = 1... 0`，`a[2] = 1`，因此第四位为`5`。
5. 最后剩余的数字为`2`，因此最后一位为`2`。
最终得到的排列为`34152`。
#### 五、总结
康拓展开和逆康拓展开是ACM竞赛中非常实用的技术之一，它们可以帮助解决许多与排列组合相关的复杂问题。通过理解和掌握这两种技术，可以更高效地解决实际问题。
