解题思路

1. 理解问题：我们需要计算给定排列在所有可能的排列中的字典序位置。排列的长度为$k$，且所有数字来自1到$n$的不重复数字。排列的排序规则是字典序。

2. 字典序排列的序号计算：对于一个给定的排列$x_1, x_2, \ldots, x_k$，我们需要计算它在所有长度为$k$的排列中的字典序位置。具体步骤如下：

   • 对于第$i$个位置$x_i$，计算在剩余可选数字中比$x_i$小的数字的个数，然后乘以$(n - i)! / (n - k)!$（对于排列）或$(n - i)$的排列数（对于组合）。
   • 由于这里是排列（顺序重要），所以对于第$i$个位置，剩余的数字是$n - i$个（因为前面的$i - 1$个数字已经被使用）。

3. 具体步骤：

   • 对于每个位置$i$（从1到$k$）：
     • 统计未被使用且小于$x_i$的数字的个数$count$。
     • 计算这些数字可以产生的排列数：$count \times (n - i) \times (n - i - 1) \times \ldots \times (n - k + 1)$（即$count \times P(n - i, k - i)$）。
     • 将这些数加到总序号中。
     • 标记$x_i$为已使用。
   • 最后的总序号加1（因为序号从1开始）。

解决代码

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

// 计算阶乘
int factorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// 计算排列数 P(n, r) = n! / (n - r)!
int permutation(int n, int r) {
    return factorial(n) / factorial(n - r);
}

int compute_permutation_order(int n, int k, const std::vector<int>& sequence) {
    std::vector<bool> used(n + 1, false); // 1-based
    int order = 0;
    for (int i = 0; i < k; ++i) {
        int current = sequence[i];
        // 统计小于当前数字且未使用的数字个数
        int count = 0;
        for (int num = 1; num < current; ++num) {
            if (!used[num]) {
                count++;
            }
        }
        // 计算排列数
        int remaining_positions = k - i - 1;
        int permutations = count * permutation(n - i - 1, remaining_positions);
        order += permutations;
        used[current] = true;
    }
    return order + 1; // 因为顺序是从0开始的，所以加1
}

int main() {
    int N;
    std::cin >> N;
    for (int assignment = 1; assignment <= N; ++assignment) {
        int n, k;
        std::cin >> n >> k;
        std::vector<int> sequence(k);
        for (int i = 0; i < k; ++i) {
            std::cin >> sequence[i];
        }
        int order = compute_permutation_order(n, k, sequence);
        std::cout << "Variace cislo " << assignment << " ma poradove cislo " << order << "." << std::endl;
    }
    return 0;
}

代码解释

1. 输入处理：首先读取任务的数量$N$。
2. 每个任务的处理：
   • 读取$n$和$k$，分别代表总人数和照片中的人数。
   • 读取给定的排列序列。
3. 计算序号：
   • 初始化一个标记数组used来记录哪些数字已经被使用。
   • 对于序列中的每个数字，统计比它小且未被使用的数字的个数count。
   • 计算这些数字可以生成的排列数：count乘以剩余位置的全排列数（使用math.perm计算排列数）。
   • 将排列数累加到order中，并标记当前数字为已使用。
4. 输出结果：最终的序号是order + 1（因为从0开始计数），并按照指定格式输出。

这种方法有效地利用了字典序排列的性质，通过逐位比较和排列数计算，高效地找到了给定排列的序号。