【题目】
传送门
题目描述：
n
n
n（
1
1
1 ≤
n
n
n ≤
20
20
20） 头牛，编号为
1...
n
1...n
1...n，正在与 FJ 玩一个疯狂的游戏。奶牛会排成一行（牛线），问 FJ 此时的行号是多少。之后，FJ 会给牛一个行号，牛必须按照新行号排列成线。
行号是通过以字典序对行的所有排列进行编号来分配的。比如说：FJ 有
5
5
5 头牛，让他们排为行号
3
3
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"，并向 FJ 问他们的行号。继续列表：
4：1 2 4 5 3 5：1 2 5 3 4
FJ 可以看到这里的答案是
5
5
5。
FJ 和奶牛希望你的帮助玩他们的游戏。他们需要
k
k
k（
1
1
1 ≤
k
k
k ≤
10000
10000
10000）组查询，查询有两个部分：
c
i
c_i
ci 将是"P"或"Q"的命令。
如果
c
i
c_i
ci 是"P"，则查询的第二部分将是一个整数
a
i
a_i
ai（
1
1
1 ≤
a
i
a_i
ai ≤
n
!
n!
n!），它是行号。此时，你需要回答正确的牛线。
如果
c
i
c_i
ci 是"Q"，则查询的第二部分将是
n
n
n 个不同的整数
b
i
,
j
b_{i,j}
bi,j（
1
1
1 ≤
b
i
,
j
b_{i,j}
bi,j ≤
n
n
n）。这将表示一条牛线，此时你需要输出正确的行号。
样例数据：
输入 5 2 P 3 Q 1 2 5 3 4
输出 1 2 4 3 5 5
【分析】
题解：康拓展开模板题
直接套用模板就可以解这道题了
贴一个同学的代码吧康拓展开&逆康拓展开
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 25
#define ll long long
using namespace std
;
int n
,m
,a
[N
];
bool vis
[N
];
ll fac
[N
];
ll
cantor()
{
ll ans
=0;
for(int i
=1;i
<=n
;++i
)
{
int num
=0;
for(int j
=i
+1;j
<=n
;++j
)
if(a
[j
]<a
[i
]) num
++;
ans
+=fac
[n
-i
]*num
;
}
return ans
;
}
void reverse_cantor(ll x
)
{
int i
,j
;x
--;
memset(vis
,false,sizeof(vis
));
for(i
=1;i
<=n
;++i
)
{
int num
=x
/fac
[n
-i
];
for(j
=1;j
<=n
;++j
)
if(!vis
[j
]&&!num
--)
break;
a
[i
]=j
;
vis
[j
]=true;
x
%=fac
[n
-i
];
}
}
int main()
{
int i
,j
;
char c
;ll x
;
scanf("%d%d",&n
,&m
);
fac
[0]=fac
[1]=1;
for(i
=2;i
<=n
;++i
)
fac
[i
]=fac
[i
-1]*i
;
for(i
=1;i
<=m
;++i
)
{
cin
>>c
;
if(c
=='P')
{
scanf("%lld",&x
);
reverse_cantor(x
);
for(j
=1;j
<=n
;++j
)
printf("%d ",a
[j
]);
printf("\n");
}
else
{
for(j
=1;j
<=n
;++j
)
scanf("%d",&a
[j
]);
x
=cantor()+1;
printf("%lld\n",x
);
}
}
return 0;
}
