代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline void Max(int &a, int b) {if (a < b) a = b;}

int n, p[20], ans;
bool v[20];

void enumer(int i, int l, int r) {
	if (i > n) ans++;
	else {
		for (int a = i; a > l; a--)
			if (!v[a]) {
				v[a] = true;
				enumer(i+1, a, r);
				v[a] = false;
			}
		for (int a = max(i,r)+1; a <= n; a++)
			if (!v[a]) {
				v[a] = true;
				enumer(i+1, l, a);
				v[a] = false;
			}
	}
}

int main() {
	int T;
	scanf("%d",&T);
	while (T--) {
		scanf("%d",&n);
		for (int i = 1; i <= n; i++)
			scanf("%d",p+i);
		memset(v,0,sizeof v);
		ans = 0;
		int l = 0, r = 1;
		for (int i = 1; i <= n; i++) {
			for (int a = max(l,p[i])+1; a <= i; a++)
				if (!v[a]) {
					v[a] = true;
					enumer(i+1, a, r);
					v[a] = false;
				}
			for (int a = max(max(i,r),p[i])+1; a <= n; a++)
				if (!v[a]) {
					v[a] = true;
					enumer(i+1, l, a);
					v[a] = false;
				}
			Max(p[i]>i ? r : l, p[i]);
			v[p[i]] = true;
		}
		printf("%d\n",ans);
	}
	return 0;
}

评测结果