1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
const int N=5000000;
int i,j,k,n,m,x,y,t,T,a[N],b[N],c[N],inv[N],fac[N],ans;
int st[N];
const int mod=998244353;
int C(int x,int y){return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
int calc(int x,int y){
if (y==0)return 1;
if (y==1)return x;
return (C(x+y-1,y)-C(x+y-1,y-2)+mod)%mod;
}
int mi(int x,int y){if (y==0)return 1;int t=mi(x,y>>1);t=1ll*t*t%mod;return y&1?(1ll*x*t%mod):t;}
int query(int x){int ans=0;for (int i=x;i;i-=i&-i)ans+=st[i];return ans;}
void add(int x){for (int i=x;i<=n;i+=i&-i)st[i]=st[i]+1;}
int main(){
scanf("%d",&T);
fac[0]=1;for (i=1;i<=1000000;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[0]=1;inv[1000000]=mi(fac[1000000],mod-2);for (i=999999;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
while (T--){
scanf("%d",&n);
for (i=1;i<=n;i++)scanf("%d",&a[i]);
memset(st,0,sizeof st);
for (i=1;i<=n;i++){c[i]=query(a[i]);add(a[i]);}
memset(st,0,sizeof st);
for (i=n;i>=1;i--){b[i]=n-i-query(a[i]);add(a[i]);}
ans=0;int cnt=1013687232;
for (i=1;i<=n;i++){
bool flag=b[i]<cnt;
if (flag)cnt=b[i];
if (!cnt)break;
ans=(ans+calc(n-i+1,cnt-1))%mod;
if (!flag&&c[i]!=a[i]-1)break;
}
printf("%d\n",ans);
}
return 0;
}
|