#P3301. [USACO2011 Feb] Cow Line

    ID: 2490 传统题 1000ms 256MiB 尝试: 277 已通过: 121 难度: 4 上传者: 标签>难度分类普及+/提高-组合数学字典序排名与反排名排列数计算CF1500Silver

[USACO2011 Feb] Cow Line

题目描述

有 NN 头奶牛,编号为 11 到 NN。农夫约翰将这 NN 个编号的全部排列按字典序从小到大排序,从 11 开始依次给它们编上行号。

例如,N=5N=5 时,字典序最小的五个排列依次是 (1,2,3,4,5)(1,2,3,4,5)、(1,2,3,5,4)(1,2,3,5,4)、(1,2,4,3,5)(1,2,4,3,5)、(1,2,4,5,3)(1,2,4,5,3) 和 (1,2,5,3,4)(1,2,5,3,4)。

一共有 KK 个询问。每次给出排列的行号求排列,或者给出一个排列求它的行号。

输入格式

从标准输入读取。第一行是两个整数 N,KN,K。每个询问占两行。

  • 第一行是 P 时,第二行是该询问的行号 AiA_i。
  • 第一行是 Q 时,第二行是 NN 个互不相同的整数,表示一个排列。

输出格式

向标准输出写入。对每个询问输出一行。P 查询输出对应排列,以空格分隔各编号。Q 查询输出给定排列的行号。

样例 1

5 2
P
3
Q
1 2 5 3 4
1 2 4 3 5
5

数据范围

1≤N≤201\le N\le20,1≤K≤100001\le K\le10000,1≤Ai≤N!1\le A_i\le N!,排列中的编号在 [1,N][1,N] 内。