uoj394

uoj394

真是一道有趣的题。。

根本想不到。。

首先我们可以打表发现这样一个事实:一个序列为好的充要条件为这个序列里没有长度为3的子序列

然后呢?

我们手模几组数据,会发现假设已经填了前i个数然后要填第i+1位

要么随便填一个比前面的最大值都大的

要么填一个最小的

所以我们可以设计一个DP

f[i][j]f[i][j]表示还剩ii个没填的数中,有jj个比当前最大值打的方案

转移很好转,每次考虑是拿更大的还是最小的。

前缀和优化一下就是

f[i][j]=f[i1][j]+f[i][j1](ji)f[i][j]=f[i-1][j]+f[i][j-1](j\leq i)

想必你已经发现了,这个ff数组就是卡特兰数!

然后怎么考虑字典序呢?

我们只要枚举一下lcp,假设当前的位置比a[i]a[i]大就行了

细节手推一下就行了

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;
}
文章目录
  1. 1. uoj394
,