代码

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=998244353;
void exgcd(ll a,ll b,ll &x,ll &y){
	b?(exgcd(b,a%b,y,x),y-=a/b*x):(x=1,y=0);
}
ll Inv(ll a){
	ll x=0,y=0;
	exgcd(a,mod,x,y);
	return(x%mod+mod)%mod;
}
ll Cat(ll n){
	ll ans=1;
	for (ll i=1;i<=n;i++) {
		ans*=4*i-2,ans%=mod;
		ans*=Inv(i+1),ans%=mod;
	}
	return ans;
}
int T,n,a[277777],b[23333];
bool check(){
	int tot=0,ans=0;
	for (int i=1;i<=n;i++) tot+=abs(i-(b[i]=a[i]));
	for (int i=1;i<=n;i++) for (int j=1;j<n;j++)
	if (b[j]>b[j+1]) swap(b[j],b[j+1]),ans++;
	return ans*2==tot;
}
void baoli(){
	int ans=0;
	while (next_permutation(a+1,a+n+1)) if (check()) ans++;
	printf("%d\n",ans%998244353);
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
			scanf("%d",a+i);
		if (n<=9) baoli(); else
		{
			for (int i=1;i<=n;i++) if (a[i]!=i) return 0;
			printf("%lld\n",Cat(n)-1);
		}
	}
	return 0;
}

评测结果