3992. 数排列
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 我们有两个大小为 $N$ 的排列 $P$ 和$ Q$（也就是说，$P $和 $Q $都是$ (1,2,...,N) $的重排）。 大小为 $N$ 的排列共有$ N! $种可能。 在这些排列中，设 $P$ 和 $Q $分别是按字典序排列时的第$ a$ 小和第$ b $小的排列。求$ ∣a-b∣$。 ## 注意 对于两个序列 $X$ 和$ Y$，当且仅当存在一个整数 $k$ 满足以下条件时，称$ X$ 按字典序小于 $Y$： - $X1=Y1,X2=Y2,...,Xk-1=Yk-1$（即前$ k-1 $项相同），且 - $Xk<Yk$。 ### 输入约束 - $2\leN\le8$ - $P$ 和$ Q $是大小为 $N $的排列。 ## 输入格式 从标准输入接收以下内容： ``` N P_1 P_2 ... P_N Q_1 Q_2 ... Q_N ``` ## 输出格式 输出 $∣a-b∣$。 ## 输入 ```in1 3 1 3 2 3 1 2 ``` ## 输出 ```out1 3 ``` ## 说明 大小为 $3$ 的排列共有 $6 $种： $(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$。 其中，$(1,3,2)$ 和$ (3,1,2) $分别是字典序第 $2 $小和第 $5 $小的排列，因此答案是 $∣2-5∣=3$。 ```in2 8 7 3 5 4 2 1 6 8 3 8 2 5 4 6 7 1 ``` ```out2 17517 ``` ```in3 3 1 2 3 ``` ```out3 0 ```