记录编号	606977	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4178.排列	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	0.499 s
提交时间	2025-10-04 20:14:11	内存使用	7.12 MiB

#include <iostream>

using namespace std;

const int N = 22;
const int MOD = 1000000007;

int n;
int nums[N];
int cc[1 << N];
int dp[1 << N];

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

int main () {
	
	freopen("changgao_perm.in", "r", stdin);
	freopen("changgao_perm.out", "w", stdout);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	dp[0] = 1;
	for (int i = 0; i < (1 << n); i++) {
		if (dp[i]) {
			int num = cc[i];
			int pick = n + 1 - num;
			int con = 0;
			for (int j = 0; j < n; j++) {
				con |= ((nums[j] >= pick) << j);
			}
			int t = i;
			for (int j = 1; j <= num; j++) {
				if (lowbit (con) > lowbit (t)) {
					goto end;
				}
				con -= lowbit (con);
				t -= lowbit (t);
			}
			for (int j = 0; j < n; j++) {
				if (!(i & (1 << j))) {
					cc[i | (1 << j)] = num + 1;
					dp[i | (1 << j)] = (dp[i | (1 << j)] + dp[i]) % MOD;
				}
			}
		}
		end:;
	}

	cout << dp[(1 << n) - 1] << endl;
	
	return 0;
}