AT_arc104_e

好题，随机讲讲。

首先期望转 LIS 长度和除以方案数。LIS 这个东西不好刻画，但是发现 $n=6$ ，所以考虑直接枚举每个数排名，也就是枚举 $X_i$ 离散化后的序列。

然后考虑知道这个序列之后怎么求方案数。先想一个弱化版的问题：有 $m$ 个数，已知他们的排名，每个数的取值范围为 $[1,k]$，$k$ 为定值。求方案数。答案显然是 $\binom{k}{m}$。

回到原问题，尝试转化成弱化版问题。注意到值域非常大（$V=10^9$）但是 $n=6$ 非常小。这启示我们，要不只有小部分值是有用的，要不可以把一段值放在一起算。这题显然是后者。

考虑把序列 $A$ 排序后去重得到序列 $B$，于是发现对于 $(B_{j-1},B_j]$ 这个区间，能取到区间内任意一个数的 $X_i$ 的集合相同。也就是说，我们如果知道了对于每个 $(B_{i-1},B_i]$，哪些 $X_i$ 在这个区间中，就可以用弱化版的方法算出每个 $i$ 的方案数，最后再乘起来即可。

这里再次暴力枚举每个排名所对应的数属于哪个 $(B_{i-1},B_i]$ 的区间即可。时间复杂度远小于 $O(n^{2n})$，轻松跑过。

code：

int n,m,a[N],b[N],c[N],d[N],lim[N],dp[N];
bool vis[N];
int ans,mx,ifac[N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1){
			ret=1ll*ret*x%mod;
		}
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
il int binom(int x,int y){
	if(x<y){
		return 0;
	}
	int s=1;
	drep(i,x,x-y+1){
		s=1ll*s*i%mod;
	}
	return 1ll*s*ifac[y]%mod;
}
int dfs2(int u,int p,int cnt){
	if(u==mx+1){
		return binom(d[p],cnt);
	}
	int ret=0;
	if(lim[u]>=b[p]){
		ret=Mod(ret,dfs2(u+1,p,cnt+1));
	}
	rep(i,p+1,m){
		if(lim[u]>=b[i]){
			ret=Mod(ret,1ll*dfs2(u+1,i,1)*binom(d[p],cnt)%mod);
		}
	}
	return ret;
}
il void solve(){
	int res=1;mx=0;
	mems(lim,0x3f);
	rep(i,1,n){
		mx=max(mx,c[i]);
		lim[c[i]]=min(lim[c[i]],a[i]);
		dp[i]=1;
		rep(j,1,i-1){
			if(c[j]<c[i]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		res=max(res,dp[i]);
	}
	ans=Mod(ans,1ll*dfs2(1,1,0)*res%mod);
}
void dfs1(int u,int p,int lst){
	if(u==n+1){
		solve();
		return;
	}
	rep(i,lst+1,n){
		if(vis[i]){
			continue;
		}
		c[i]=p,vis[i]=1;
		dfs1(u+1,p,i);
		if(u<n){
			dfs1(u+1,p+1,0);
		}
		vis[i]=0;
	}
}
void Yorushika(){
	read(n);
	int fac=1,s=1;
	rep(i,1,n){
		read(a[i]),b[i]=a[i];
		fac*=i;
		ifac[i]=qpow(fac,mod-2);
		s=1ll*s*a[i]%mod;
	}
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	rep(i,1,m){
		d[i]=b[i]-b[i-1];
	}
	dfs1(1,1,0);
	printf("%lld\n",1ll*ans*qpow(s,mod-2)%mod);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}