代码

#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
typedef long long int64;
const int N=6e5+1;
const int mod=998244353;
int n,p[N],fac[N],ifac[N];
class FenwickTree {
	private:
		int val[N];
		int lowbit(const int &x) const {
			return x&-x;
		}
	public:
		void reset() {
			std::fill(&val[1],&val[n]+1,0);
		}
		void modify(int p) {
			for(;p<=n;p+=lowbit(p)) {
				val[p]++;
			}
		}
		int query(int p) const {
			int ret=0;
			for(;p;p-=lowbit(p)) {
				ret+=val[p];
			}
			return ret;
		}
};
FenwickTree t;
inline int C(const int &n,const int &m) {
	return (int64)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void exgcd(const int &a,const int &b,int &x,int &y) {
	if(!b) {
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
inline int inv(const int &x) {
	int ret,tmp;
	exgcd(x,mod,ret,tmp);
	return (ret%mod+mod)%mod;
}
int main() {
	for(register int i=fac[0]=1;i<N;i++) {
		fac[i]=(int64)fac[i-1]*i%mod;
	}
	ifac[N-1]=inv(fac[N-1]);
	for(register int i=N-1;i;i--) {
		ifac[i-1]=(int64)ifac[i]*i%mod;
	}
	for(register int T=getint();T;T--) {
		n=getint();
		bool increase=true;
		for(register int i=1;i<=n;i++) {
			p[i]=getint();
			if(p[i]!=i) increase=false;
		}
		if(increase) {
			printf("%d\n",int(((int64)C(n*2,n)*inv(n+1)%mod-1+mod)%mod));
			continue;
		}
		int ans=0;
		while(std::next_permutation(&p[1],&p[n]+1)) {
			int sum=0;
			for(register int i=1;i<=n;i++) {
				sum+=std::abs(i-p[i]);
			}
			sum/=2;
			t.reset();
			int tmp=0;
			for(register int i=n;i>=1;i--) {
				tmp+=t.query(p[i]);
				t.modify(p[i]);
			}
			if(tmp==sum) (++ans)%=mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}

评测结果