深入浅出，解析 《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;
}