P3014 [USACO11FEB] Cow Line S

编号为 $1$ 到 $N (1 \leq N \leq 20)$ 的 $N$ 头奶牛正在和农夫约翰玩他们的又一个疯狂游戏。奶牛们将自己排列成一行，并询问农夫约翰它们的排列编号是多少。作为回应，农夫约翰可以给它们一个排列编号，奶牛们必须重新排列成那个排列。 排列编号是通过按字典序给所有排列编号来分配的。 考虑这个例子： 农夫约翰有 $5$ 头奶牛，并给它们排列编号 $3$ 。 按升序字典序排列的排列：第 $1$ 个：$1,2,3,4,5$ 第 $2$ 个：$1,2,3,5,4$ 第 $3$ 个：$1,2,4,3,5$ 因此，奶牛们将自己排列成奶牛排列 $1,2,4,3,5$。 奶牛们反过来排列成配置「$1,2,5,3,4$」，并询问农夫约翰它们的排列编号是多少。 继续列表： 第 $4$ 个：$1,2,4,5,3$ 第 $5$ 个：$1,2,5,3,4$ 农夫约翰可以看到答案是 $5$ 。 农夫约翰和奶牛们希望你能帮助他们玩这个游戏。他们有 $K (1 \leq K \leq 10,000)$ 个查询需要帮助。查询 $i$ 有两个部分：$C_i$ 是命令，可以是 `P` 或 `Q` 。 如果 $C_i$ 是 `P` ，那么查询的第二部分将是一个整数 $A_i (1 \leq A_i \leq N!)$，这是一个排列编号。这是农夫约翰挑战奶牛们排成正确的奶牛排列。 如果 $C_i$ 是 `Q`，那么查询的第二部分将是 $N$ 个不同的整数 $B_{ij} (1 \leq B_{ij} \leq N)$。这将表示一个奶牛排列。这是奶牛们挑战农夫约翰找出它们的排列编号。

\* 第 $1$ 行：两个用空格分隔的整数：$N$ 和 $K$ \* 第 $2$ 行到第 $2 \times K + 1$ 行：第 $2 \times i$ 行和第 $2 \times i + 1$ 行将包含一个查询。 第 $2 \times i$ 行将只包含一个字符：如果奶牛们排列并询问农夫约翰它们的排列编号，则为 `Q`；如果农夫约翰给奶牛们一个排列编号，则为 `P`。 如果第 $2 \times i$ 行是 `Q`，那么第 $2 \times i + 1$ 行将包含 $N$ 个用空格分隔的整数 $B_ij$，表示奶牛排列。如果第 $2 \times i$ 行是 `P`，那么第 $2 \times i + 1$ 行将包含一个整数 $A_i$，这是要解决的排列编号。

\* 第 $1$ 行到第 $K$ 行：第 $i$ 行将包含查询 $i$ 的答案。 如果输入的第 $2 \times i$ 行是 `Q`，那么这一行将包含一个整数，即第 $2 \times i + 1$ 行中奶牛排列的排列编号。 如果输入的第 $2 \times i$ 行是 `P`，那么这一行将包含 $N$ 个用空格分隔的整数，给出第 $2 \times i + 1$ 行中编号的奶牛排列。

（由 ChatGPT 4o 翻译）