阶乘进制 (Factorial Number System) 原理介绍

阶乘进制，又称为 Lehmer 码 (Lehmer code)，是一种混合基数系统 (Mixed Radix System)，它使用阶乘作为每一位的权值（基数），而不是像传统的 进制（如十进制、二进制）那样使用 的幂作为权值。

1. 核心思想

阶乘进制的核心思想是：任何一个非负整数 都可以唯一地表示为一系列系数乘以对应阶乘之和。

2. 表示形式

一个非负整数 在阶乘进制下可以表示为：

其中，每一位 的权值（基数）是 （ 的阶乘）。

数学表达式为：

3. 系数（数字）的限制

这是阶乘进制最关键的特征之一。每一位上的系数 都有严格的取值范围，它取决于该位的权值 ：

权值 () 位的索引 () 系数 () 的取值范围

注意： 最低位 的权值是 ，其系数 只能取 (因为 )。所以，在实际表示中，阶乘进制的最低位 常常被省略或约定为 。

4. 应用：排列和 Lehmer 码

阶乘进制最著名的应用是在排列 (Permutations) 领域：

  • 对于 个元素的集合，总共有 种不同的排列方式。
  • 阶乘进制的 范围内的每一个数，都唯一对应一个 个元素的排列。这个数就是该排列的 Lehmer 码。
  • 系数 在排列中代表了在当前剩下的元素中，第 个位置的元素是第 小的元素（基于 0-索引）。

简而言之，阶乘进制提供了一种将排列和整数进行双射（一一对应）编码的方法。

算法思路

直接使用字典序枚举 N! 种排列在 N=20 时是不可能的。
取而代之的是 阶乘进制（Factorial Number System，亦称 Lehmer 码）。

根据上述讨论过的阶乘进制：

  1. 个数的排列总共有 种。
  2. 通过阶乘进制，我们可以将任意一个排列映射为一个唯一的整数（排名），反之亦然。

1. 预处理阶乘

由于 ，我们需要预先计算 到 的值。 注意：，这在 C++ 中可以用 unsigned long long (64位无符号整数) 存储（最大约 ）。

2. 操作 P：已知排名找排列（逆康托展开）

输入是 1-based 的排名 ，首先将其转化为 0-based（即 ）。 我们维护一个可用数字列表（初始为 ）。

从第 1 位到第 位，对于第 位（从 0 开始计数）：

  1. 该位的权值是 。
  2. 计算系数：。
  3. 这个系数 表示我们需要从当前剩余的可用数字列表中取出第 个数字（0-索引）。
  4. 输出该数字，并从列表中删除它。
  5. 更新排名：。

3. 操作 Q：已知排列找排名（康托展开）

我们需要计算有多少个排列的字典序小于当前给定的排列。 结果初始为 。

对于排列中的每一个数 （位置记为 ，从 0 开始）：

  1. 查看在这个数之后的位置（或者简单的说，在未被使用的数字集合中），有多少个数字比 小。记为 。
  2. 该位对排名的贡献为 。
  3. 。
  4. 标记 为已使用。

最后输出 （转回 1-based 排名）。

代码实现

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;
using ll = unsigned long long;

// 使用 unsigned long long 防止溢出，20! 约为 2.4e18，而 unsigned long long 的最大值约为 1.8e19 （即 2^64−1）。
array<ll, 21> fact;

// 预处理阶乘
void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= 20; i++) {
        fact[i] = fact[i - 1] * i;
    }
}

// 操作 P: 根据排名找排列 (逆康托展开)
void solveP(int n, long long rank) {
    rank--; // 将 1-based 排名转换为 0-based
    vector<int> available;
    // 初始化可用数字列表 1 到 N
    for (int i = 1; i <= n; i++) available.push_back(i);

    for (int i = 0; i < n; i++) {
        ll f = fact[n - 1 - i]; // 当前位的阶乘权值
        int idx = rank / f;            // 确定选第几个剩下的数
        rank %= f;                     // 更新 rank 为余数

        // 输出选中的数
        cout << available[idx] << (i == n - 1 ? "" : " ");

        // 从可用列表中移除该数
        available.erase(available.begin() + idx);
    }
    cout << endl;
}

// 操作 Q: 根据排列找排名 (康托展开)
void solveQ(int n, vector<int>& perm) {
    ll rank = 0;
    // 用于标记数字是否已经出现过
    vector<bool> used(n + 1, false);

    for (int i = 0; i < n; i++) {
        int val = perm[i];
        int smaller_count = 0;

        // 统计有多少个比当前数小且未被使用过的数
        // 因为 N 最大才 20，直接循环统计即可，复杂度 O(N^2) 对每组查询都很快
        for (int j = 1; j < val; j++) {
            if (!used[j]) smaller_count++;
        }

        // 累加当前位的贡献
        rank += smaller_count * fact[n - 1 - i];
        used[val] = true;
    }

    // 输出 1-based 排名
    cout << rank + 1 << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int N, K;
    if (cin >> N >> K) {
        for (int k = 0; k < K; k++) {
            char type;
            cin >> type;
            if (type == 'P') {
                long long r;
                cin >> r;
                solveP(N, r);
            } else {
                vector<int> perm(N);
                for (int i = 0; i < N; i++) {
                    cin >> perm[i];
                }
                solveQ(N, perm);
            }
        }
    }
    return 0;
}