代码

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<cstdio>
#include<cctype>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=600005;
const ll mod=998244353;
int n,m,T,p[maxn];
ll h[maxn];
namespace {
    inline ll Pow(ll a,ll b) {
        ll res=1;
        while(b) {
            if(b&1)
                res=res*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return res;
    }
    inline ll Inv(const ll &x) {
        return Pow(x,mod-2);
    }
    inline ll Add(const ll &x,const ll &y) {
        ll res=x+y;
        if(res>=mod)
            res-=mod;
        return res;
    }
    inline ll Sub(const ll &x,const ll &y) {
        ll res=x-y;
        if(res<0)
            res+=mod;
        return res;
    }
    inline ll Mul(const ll &x,const ll &y) {
        ll res=x*y;
        if(res>=mod)
            res%=mod;
        return res;
    }
    inline ll Div(const ll &x,const ll &y) {
        ll res=x*Inv(y);
        if(res>=mod)
            res%=mod;
        return res;
    }
}
int bit[10];
int ans[10][362881];
unordered_map<ll,int>rev[10];
int q[10];
inline int lb(int x) {
	return x&(-x);
}
inline void add(int x,int y) {
	for(;x<=y;x+=lb(x))
		bit[x]++;
}
inline int que(int x) {
	int res=0;
	for(;x;x-=lb(x))
		res+=bit[x];
	return res;
}
inline void init(int x) {
	for(int i=1;i<=x;++i)
		q[i]=i;
	int cnt=0;
	do {
		int flg1=0,flg2=0;
		ll flg3=0;
		for(int i=1;i<=x;++i)
			flg1+=abs(i-q[i]),flg2+=i-1-que(q[i]),add(q[i],x),flg3=flg3*x+(q[i]-1);
		if(flg1/2==flg2)
			ans[x][cnt]++;
		rev[x][flg3]=cnt;
		cnt++;
		for(int i=1;i<=x;++i)
			bit[i]=0;
	}while(next_permutation(q+1,q+x+1));
	for(int i=cnt-1;~i;--i)
		ans[x][i]+=ans[x][i+1];
//		,cout<<ans[x][i]<<" ";
//	cout<<endl;
}
inline void File() {
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
}
int main() {
	File();
	h[0]=1;
	for(int i=1;i<=300000;++i)
		h[i]=Mul(Mul(h[i-1],4*i-2),Inv(i+1));
	for(int i=1;i<=9;++i)
		init(i);//,cerr<<i<<endl;
	read(T);
	while(T--) {
		read(n);
		bool flg=1;
		for(int i=1;i<=n;++i)
			read(p[i]),flg&=(p[i]==i);
		if(n<=9) {
			ll now=0;
			for(int i=1;i<=n;++i)
				now=now*n+(p[i]-1);
			printf("%d\n",ans[n][rev[n][now]+1]);
			continue;
		}
		if(flg) {
			printf("%lld\n",h[n]-1);
			continue;
		}
	}
}

评测结果