#欢乐赛42 T4题解

由于n = 10,如果你打算强行列出所有的组合,恭喜你会像讨论区里的某位小萌新一样爆内存。
这里,我们给出一个高效的求解方法：
AC代码为：

#include <bits/stdc++.h>

using namespace std;

int n,m;
int main() 
{
    cin >> n >> m;
    
    vector<int> factorials(n + 1, 1);
    for (int i = 1; i <= n; ++i) 
        factorials[i] = factorials[i - 1] * i;
    
    vector<int> nums;
    for (int i = 1; i <= n; ++i) 
        nums.push_back(i);
    
    int k = m - 1; // 转换为0-based索引
    vector<int> result;
    
    for (int i = 0; i < n;i++)
    {
        int remaining = n - i;
        int fact = factorials[remaining - 1];
        int index = k / fact;
        
        result.push_back(nums[index]);
        nums.erase(nums.begin() + index);
        k %= fact;
    }
    
    for (int i = 0; i < result.size();i++)
    {
        if (i > 0) 
            cout << " ";
        cout << result[i];
    }
    
    return 0;
}

简单解释:
先预计算阶乘结果用于快速计算剩余组合数，每次循环计算当前位的剩余数字数量remaining，用k / fact确定当前应选数字的索引，将选中的数字加入结果并从候选列表中移除，更新k为剩余索引，进入下一位计算，这样我们就将数字逐位确定了，然后循环完了输出结果就行。
0ms,3.5M的速度和空间消耗,应该没人比我更低了吧.