期望。
Solution
- 显然我们会发现 \(n\) 非常的小。同时，LIS 的大小取决于数与数之间的大小关系。
所以我们可以把序列“离散化”，枚举大小关系的情况。
需要注意的是，数可以相同。所以枚举的离散化序列可能是1 3 3 2 4 2这样的。
所以枚举离散化序列的方案数是 \(6!\)（至多），大致是 \(800\) 种，可以接受。 - LIS 的长度我们显然可以通过离散化序列在常数复杂度下得到。
- 考虑枚举完一种相对大小关系序列之后如何统计取数的方案数。
经过简单思考发现，每个数的取值范围都是不同的，且在此基础上还要满足序列中大小关系的限制。
进一步地，我们发现，假如现在我们有 \(x\) 个大小关系不同的数，它们都在某个长度为 \(len\) 的值域区间，那么它们的取数方案即显然是 \(C_{len}^x\)，每次选完之后直接按照大小关系一一对应即可。 - 所以我们可以考虑根据两种限制把值域取值划分为若干段。
然后按照离散化序列从小到大暴力枚举第 \(i\) 大的数可以存在于哪一段值域区间，最后使用上述组合数的方法统计即可。 - 总的来说，时间复杂度基于 \(n\)，而 \(n\) 非常小，实际 \(O(n!^2)\) 跑不满。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
const int mod = 1e9 + 7, maxn = 2e5 + 5, inf = 0x3f3f3f3f3f;
int n, a[maxn], b[maxn], c[maxn], d[maxn];
int f[maxn], p[maxn], q[maxn], len, mx;
int ans, inv[maxn], lim[maxn], cnt, tg[maxn];
inline int pw(int x, int p){
int res = 1ll;
while(p){
if(p & 1) res = res * x % mod;
p /= 2, x = x * x % mod;
} return res;
}
inline int C(int n, int m){
if(m > n) return 0;
int res = 1;
rep(i, 1, m) (res *= n - i + 1) %= mod;
return res * inv[m] % mod;
}
inline void dfs2(int nw, int lst){
if(nw > mx){
int as = 1; rep(i, 1, cnt) d[i] = 0;
rep(i, 1, mx) d[c[i]] += 1;
rep(i, 1, cnt) (as *= 1ll * C(p[i], d[i])) %= mod;
(ans += 1ll * as * len % mod) %= mod;
return;
}
rep(i, lst, cnt) if(lim[nw] >= q[i])
c[nw] = i, dfs2(nw + 1, i);
}
inline void calc(){
cnt = len = 0; rep(i, 1, mx) lim[i] = inf; rep(i, 1, n) f[i] = 0;
rep(i, 1, n) lim[b[i]] = min(lim[b[i]], a[i]);
per(i, mx - 1, 1) lim[i] = min(lim[i], lim[i + 1]);
rep(i, 1, mx) if(lim[i] - lim[i - 1])
p[++cnt] = lim[i] - lim[i - 1], q[cnt] = lim[i];
rep(i, 1, n) rep(j, 0, i - 1)
if(b[j] < b[i]) f[i] = max(f[i], f[j] + 1);
rep(i, 1, n) len = max(len, f[i]);
dfs2(1, 1);
}
inline void dfs(int nw){
if(nw > n){
mx = 0; rep(i, 1, n) mx = max(mx, b[i]);
rep(i, 1, n) tg[i] = 0; rep(i, 1, n) tg[b[i]] += 1;
rep(i, 1, mx) if(!tg[i]) return;
calc(); return;
}
rep(i, 1, n) b[nw] = i, dfs(nw + 1);
}
signed main(){
scanf("%lld", &n);
int p = 1; rep(i, 1, n) (p *= 1ll * i) %= mod;
inv[n] = pw(p, mod - 2), inv[0] = 1;
per(i, n - 1, 1) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
rep(i, 1, n) scanf("%lld", &a[i]);
dfs(1);
rep(i, 1, n) (ans *= 1ll * pw(a[i], mod - 2) % mod) %= mod;
printf("%lld", ans);
return 0;
}
Thanks for reading.