代码

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

#define REP(i,a,b) for(int i=a;i<=b;++i)
#define DREP(i,a,b) for(int i=a;i>=b;--i)
typedef long long ll;

using namespace std;

void File(){
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
}

const int maxn=6e5+10;
const int maxw=(1<<19)+10;
const ll mod=998244353;
int T,n,a[maxn];
ll dp[20][maxw];

int bit(int x){return 1<<(x-1);}
int count(int x,int y){return __builtin_popcount(x>>y);}

bool vis[maxn];
ll cal(int x,int len){
	memset(dp,0,sizeof(dp));
	int all=0,las=0;
	REP(i,1,n)if(!vis[i])all|=bit(i);
	else if(i!=x)las|=bit(i);
	all|=bit(x);
	dp[1][bit(x)]=1;
	if(count(las,x)>max(n-len+1-x,0))return 0;
	REP(i,2,len){
		REP(j,1,n){
			if(j==x)continue;
			if(!(bit(j)&all))continue;
			int S0=all^bit(j);
			for(int S=S0;S;S=(S-1)&S0){
				if(!(bit(x)&S))continue;
				if(__builtin_popcount(S)!=i-1)continue;
				int low=n-len+i;
				if(count(S|las,j)>max(low-j,0))continue;
				dp[i][S^bit(j)]=(dp[i][S^bit(j)]+dp[i-1][S])%mod;
			}
		}
	}
	return dp[len][all];
}

ll ans;

int main(){
	//File();
	scanf("%d",&T);
	while(T--){
		ans=0;
		memset(vis,0,sizeof(vis));
		scanf("%d",&n);
		REP(i,1,n){
			scanf("%d",&a[i]);
			vis[a[i]]=1;
		}
		DREP(i,n,1){
			vis[a[i]]=0;
			bool flag=false;
			REP(j,1,i-1){
				int cnt=0;
				REP(k,1,j-1)if(a[k]>a[j])++cnt;
				if(cnt>max(j-a[j],0)){
					flag=true;
					break;
				}
			}
			if(flag)continue;
			REP(j,a[i]+1,n)if(!vis[j]){
				vis[j]=1;
				ans=(ans+cal(j,n-i+1))%mod;
				vis[j]=0;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果