代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

const int N=20;
const int MX=(1<<N)+10;

int n,S,p[N];

int dp[2][N][MX];

bool check(int s,int p,int x)
{
	if((s>>x)&1)
		return false;
	int t=(1<<x)-1;
	if(p>=x)
		return t==(s&t);
	else
		return (s&(S^t))==0;
}

int dfs(int lim,int nw,int s)
{
	int& res=dp[lim][nw][s];
	if(~res)
		return res;
	if(nw==n)
	{
		res=!lim;
		return res;
	}
	res=0;
	if(lim)
	{
		for(int i=p[nw];i<n;++i)if(check(s,nw,i))
			res+=dfs(i==p[nw],nw+1,s^(1<<i));
	}
	else
	{
		for(int i=0;i<n;++i)if(check(s,nw,i))
			res+=dfs(0,nw+1,s^(1<<i));
	}
	return res;
}

void work()
{
	scanf("%d",&n);
	S=(1<<n)-1;
	for(int i=0;i<n;++i)
	{
		scanf("%d",p+i);
		--p[i];
	}
	memset(dp,-1,sizeof dp);
	printf("%d\n",dfs(1,0,0));
}

int main()
{
	//freopen("inverse.in","r",stdin);
	//freopen("inverse.out","w",stdout);
	int T;
	for(scanf("%d",&T);T--;)
		work();
	return 0;
}

评测结果