对楼上那为大佬的补充

首先前面讲解的都很清楚了，

当前集合排序后<=原数组前len个排序后

对于一次交换 $i<j,a_i>a_j$，如果交换的位置都在前缀 $1\sim k$ 内，那么前缀里的数字集合不变；如果一个位置在前缀内，一个在后缀，那么前缀中会进入一个更小的数字。因此可以发现：无论进行多少次操作，任意前缀排序后的结果都不会比原排列对应前缀排序后的结果更大。

所以一个排列 $b$ 可以被生成，当且仅当对于所有 $i$，满足：

$$sort(b_1,b_2,\dots,b_i)\le sort(a_1,a_2,\dots,a_i)$$

其中比较是逐位比较。

因为 $n\le20$，考虑状压 DP。我们不枚举最终排列，而枚举当前前缀选择了原排列中的哪些位置。设 $dp[S]$ 表示：集合 $S$ 中的位置对应的数字，可以组成一个合法前缀。若 $|S|=k$，说明当前已经确定了前 $k$ 个位置。

转移时枚举一个没有加入的位置 $x$，令：

$$T=S\cup\{x\}$$

如果集合 $T$ 满足前缀限制，则：

$$dp[T]+=dp[S]$$

判断一个集合是否合法，只需要将集合中的数字排序，与原数组前 $|S|$ 个数字排序后比较即可。

最终所有位置都被选择：

$$S=(1<<n)-1$$

答案就是：

$$dp[S]$$

深入浅出，解析 《WZH题解》

为什么是这个性质？

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

充分性证明

首先，为什么，我们可以操作出整体更小的排列？ 这是一个充分性问题。

对于排列的前 $k$ 位，$a[1, k]$。 分类讨论，交换行为对于它的影响。

• 情况一：$i \lt j \le k$。$a[1, k]$ 的元素集不变，满足要求。

• 情况二：$i \le k \lt j$。$a[1, k]$ 的元素集移除了 $a_i$，加入了 $a_j$。因为 $a_i \lt a_j$，因此元素集变小，满足要求。

• 情况三：$k \le i \lt j$。对于 $a[1, k]$ 的元素集没有任何影响，满足要求。

必要性证明，方法 1

然后，为什么，我们只能操作出整体更小的排列？ 这是一个必要性问题。

交换元素只有上述的三种情况，每一个都不能让 $a[1, k]$ 的元素集变大（即整体变大）。 初始状态的元素集满足要求，因此无论操作多少次，元素集都会一直满足要求。

必要性证明，方法 2

不满足要求的一定不可到达。
但题目只有这一种限制。
那么剩下的情况，也即满足要求的情况，是一定可到达的。

综上所述，满足要求的排列 = 我们可以操作出的排列。

如何 dp？

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

对于状压元素集合。
具体地，设 $f(i, s)$ 代表 $a[1, i]$ 的元素集合为 $s$ 的排列数量。

初始化 $f(0, 0) = 1$。

• 如果 $s$ 满足要求，$f(i, s) = \sum_{e \in s} f(i-1, s \setminus \{e\})$。
• 否则 $f(i, s) = 0$。

最终答案 $f(n, \Omega)$。

#include<bits/stdc++.h>
#define popc __builtin_popcount
using namespace std;
const int N = 21, M = (1<<N), P = 1e9 + 7;
int n, a[N], f[2][M];

int lowbit(int x){ return x & (-x); }

bool check(int x, int y){
	//x 整体小于等于 y
	while(x > 0){
		if(lowbit(x) > lowbit(y)) return false;
		x ^= lowbit(x);
		y ^= lowbit(y);
	}
	return true;
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i], a[i]--;
	int now = 0;
	f[0][0] = 1;
	for(int i = 1; i <= n; i ++){
		now = now | (1<<a[i]);
		memset(f[i&1], 0, sizeof f[i&1]);
		for(int s = 0; s < (1<<n); s ++){
			if(popc(s) != i) continue;
			if(!check(s, now)) continue;
			int t = s;
			while(t>0){
				f[i&1][s] = (1ll * f[i&1][s] + f[(i-1)&1][s^lowbit(t)]) % P; 
				t ^= lowbit(t);
			}
		}
	}
	cout << f[n&1][(1<<n)-1];
	return 0;
}

排列（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)$。