代码

//#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<assert.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1LL<<62;
const int mod=998244353;

const int N=2e6+100;

int qpow(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=1LL*ans*x%mod;
		x=1LL*x*x%mod;y>>=1;
	}
	return ans;
}

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

namespace io {
	const int L=(1<<21)+1;
	char ibuf[L],*iS,*iT,obuf[L],*oS=obuf,*oT=obuf+L-1,c,st[55];int f,tp;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline char getc() {
		return gc();
	}
	inline void flush() {
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	inline void putc(char x) { *oS++=x; if (oS==oT) flush(); }
	template<class I> inline void gi(I&x) {
		for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
		for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15); x*=f;
	}
	template<class I> inline void print(I x) {
		if (!x) putc('0');
		if (x<0) putc('-'),x=-x;
		while (x) st[++tp]=x%10+'0',x/=10;
		while (tp) putc(st[tp--]);
	}
	inline void gs(char*s, int&l) {
		for (c=gc();c<'a'||c>'z';c=gc());
		for (l=0;c<='z'&&c>='a';c=gc()) s[l++]=c;
		s[l]=0;
	}
	inline void ps(const char*s) { for (int i=0,n=strlen(s);i<n;i++) putc(s[i]); }
	struct IOFLUSHER{ ~IOFLUSHER() { flush(); } } _ioflusher_;
};
using io::getc;
using io::putc;
using io::gi;
using io::gs;
using io::ps;
using io::print;

int c[N];
int fac[N],inv[N];
int sum(int x) { return x?c[x]+sum(x^(x&-x)):0; }
int C(int n,int m) {
	if (m<0||n<m) return 0;
	return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int S(int n,int m) {
	return (C(n+m+1,n+1)-C(n+m+1,n+2)+mod)%mod;
}
int main()
{
	freopen("inverse.in","r",stdin);
	freopen("inverse.out","w",stdout);
	int T,n=1e6,i,t,a,b,ans,w,x;
	gi(T);
	for (i=fac[0]=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
	for (i=2,inv[0]=inv[1]=1;i<=n;i++) inv[i]=mod-1LL*(mod/i)*inv[mod%i]%mod;
	for (i=3;i<=n;i++) inv[i]=1LL*inv[i]*inv[i-1]%mod;
	while (T--) {
		gi(n);
		for (t=1;t<=n;t++) c[t]=0;
		for (i=1;i<=n;i++) for (t=i;t<=n;t+=t&-t) ++c[t];
		a=b=0;
		ans=0;
		for (i=1;i<=n;i++) {
			gi(x);
			w=n-i+1;
			if (x>a) (ans+=S(w-1,sum(n)-sum(x)-1))%=mod,a=x;
			else if (x>b) {
				(ans+=S(w-1,sum(n)-sum(a)-1))%=mod;
				if (sum(x)-sum(b)!=1) break;
				b=x;
			} else {
				(ans+=S(w-1,sum(n)-sum(a)-(sum(a)==sum(b))))%=mod;
				break;
			}
			for (t=x;t<=n;t+=t&-t) --c[t];
			if (sum(b)) break;
		}
		while (++i<=n) gi(x);
		print(ans);
		putc('\n');
	}
	return 0;
}

评测结果