Count Order

题目描述

我们有两个大小为 $N$ 的排列 $P$ 和 $Q$（也就是说，$P$ 和 $Q$ 都是 $(1,~2,~...,~N)$ 的重排）。 大小为 $N$ 的排列共有 $N!$ 种可能。在它们当中，令 $P$ 和 $Q$ 分别是按字典序第 $a$ 个和第 $b$ 个最小的排列。求 $|a - b|$。

输入格式

输入从标准输入给出，格式如下： $N$ $P_1$ $P_2$ $...$ $P_N$ $Q_1$ $Q_2$ $...$ $Q_N$

输出格式

输出 $|a - b|$。

3
1 3 2
3 1 2

3

8
7 3 5 4 2 1 6 8
3 8 2 5 4 6 7 1

17517

3
1 2 3
1 2 3

0

提示

$2 \leq N \leq 8$ $P$ 和 $Q$ 是大小为 $N$ 的排列。对于两个序列 $X$ 和 $Y$，当且仅当存在整数 $k$ 使得 $X_i = Y_i~(1 \leq i < k)$ 且 $X_k < Y_k$ 时，称 $X$ 在字典序上小于 $Y$。大小为 $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$。

标签: AtCoder|abc150C

来源

AtCoder|abc150C