这是一个好题,感觉是noi2018里面最好的题目,考验打表能力,动态规划和对卡特兰数的理解。  

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int const N=1000000+10;
 4 int const mod=998244353;
 5 int n,a[N],pw[N<<1],inv[N<<1],vis[N];
 6 int ksm(int x,int y){
 7     int ret=1;
 8     while (y){
 9         if(y&1) ret=1LL*ret*x%mod;
10         x=1LL*x*x%mod;
11         y>>=1;
12     }
13     return ret;
14 }
15 int calc(int x,int y){
16     if(x<y) return 0;
17     return 1LL*pw[x]*inv[y]%mod * inv[x-y]%mod;
18 }
19 int main(){
20     //freopen("inverse.in","r",stdin);
21     //freopen("inverse.out","w",stdout);  
22     int cas;
23     scanf("%d",&cas);
24     pw[0]=1;
25     for(int i=1;i<=2000000;i++)
26         pw[i]=1LL*pw[i-1]*i%mod;
27     inv[2000000]=ksm(pw[2000000],mod-2);
28     for(int i=1999999;i>=0;i--)
29         inv[i]=1LL*inv[i+1]*(i+1)%mod;
30     while (cas--){
31         scanf("%d",&n);
32         for(int i=1;i<=n;i++)
33             scanf("%d",&a[i]);
34         int mv=0,ans=0,mn=1;
35         memset(vis,0,sizeof(vis));
36         for(int i=1;i<=n;i++){
37             int lim=max(mv+1,a[i]+1);
38             vis[a[i]]=1;
39             if(lim<=n)
40                 ans=((ans+calc(2*n-i-lim+1,n-i+1)-calc(2*n-i-lim+1,n-i+2))%mod + mod) % mod;
41             if(a[i]>mv) mv=a[i];
42             else if(a[i]!=mn)  break;
43             while (vis[mn]) mn++;
44         }
45         printf("%d\n",ans);
46
47     }
48     return 0;
49 }
View Code
02-11 14:54