排列（perm）

一个排列 $a$，每次你可以交换一个逆序对。求你可以生成多少个不同的排列。

$n\le 20$。

考虑如何判断一个排列 $p$ 是否能被生成。我们拿样例举例：

样例： 2 4 1 3。

首先我们先观察所有排列的第一项：显然，如果一个排列的第一项为 $3,4$，即 $>a_1$，那么这种排列肯定不行，原因是一个数能被交换到首位，必然需要和 $a_1$ 交换。

那么我们就可以排除掉 $12$ 个排列。

然后我们看 $a_2$：由于 $a_2$ 是 $4$，这导致我们什么也排除不掉。

接着看 $a_3$：$a_3$ 是 $1$，那么，对于所有的排列，前 $3$ 位中没有 $1,2$ 的排列肯定也不行，因为如果是这样的话，原序列前 $3$ 位的 $1,2$ 必须被换到后面去，然而并没有数能把它换到后面去，所以所有前 $3$ 不包含 $1,2$ 的排列必然不行。

这样就只剩下 $8$ 个排列了，恰好是答案。

思考一下上面排除方案的本质：对于 $i<j$，若 $a_i>a_j$，则交换后，前 $i$ 位的所有数字必然整体越来越小，即，尽管我不能确认每一位具体是谁，但是我可以保证，新的排列的前 $i$ 位，必然整体要小一些，或者说，新的排列前 $i$ 位排序后的每一个数字必然 $\le$ 原来排列前 $i$ 位排序的每一个数字。

总结一下刚才的推论：一个排列能被生成，当且仅当对于每一个 $i\in[1,n]$，这个排列的前 $i$ 位排序后，对位必须 $\le$ 原来的排列前 $i$ 位排序后的结果。

剩下就是简单的状压 DP 了，时间复杂度 $\mathcal{O}(n2^n)$。