题意
给定一个长度为 \(N\) 的序列 \(A\)，按照下列方式生成一个长度为 \(N\) 的序列 \(X\)：
\(\forall i\in[1,n]\)，\(X_i\) 在 \([1,A_i]\) 中的整数中均匀随机生成。
求其最长上升子序列长度的期望，对 \(10^9+7\) 取模。
\(1 \le N \le 6, 1 \le A_i \le 10^9\)。
题解
由于 \(N\) 很小，故我们可以直接枚举 \(X_i\) 的排名，然后计算其贡献。
发现并非所有的 \(N^N\) 种情况都是合法的，例如当 \(N = 3\) 时，排名序列 \(\left\{1,1,3\right\}\) 就是不合法的，而排名序列 \(\left\{1,1,2\right\}\) 是合法的。所有可能的合法排名序列叫做有序贝尔数，其 OEIS 编号为 A000670。当 \(N = 6\) 时，其值为 \(4683\)。
现在问题变为了，在钦定的排名序列下，求最长上升子序列的长度和取到该排名的序列的方案数。
前者是平凡的，由于 \(N\) 很小，故可以肆意求。
现在考虑如何求方案数，首先我们可以将排名相同的数视为一类数，设我们有 \(M\) 类书，那么对于每一类数我们可以求出其最大取值为多少，设其为 \(H_i\)，其中 \(H_0 = 0\)，那么我们可以得出随着排名递减 \(H_i\) 应也为递减的，即 \(\forall i \in \left[1， M\right), H_i \le H_{i + 1}\)，若存在 \(i \in \left[1， M\right)\)，使得$ H_i > H_{i + 1}$，那么更新 \(H_i \leftarrow \min\left\{H_i, H_{i + 1}\right\}\) 即可。
可以发现数的取值范围是 \(\mathcal{O}(M)\) 个区间，故我们可以按区间去考虑，设 \(f_{i, j}\) 表示前 \(i\) 个区间中有 \(j\) 个数的方案数，通过枚举前 \(i - 1\) 个区间中有多少个数即可实现转移，因为钦定了前 \(i - 1\) 个区间中有多少个数，不妨设其为 \(k\)，那么区间 \(\left(H_{i - 1}, H_{i}\right]\) 中的数有 \(j - k\) 种，其方案数为 \(\dbinom{H_{i} - H_{i - 1}}{j - k}\)，至此可以写出转移式
初始状态为 \(f_{0, 0} = 1\)，答案状态为 \(f_{M, M}\)，这部分的复杂度为 \(\mathcal{O}(N^3)\)。
设 \(a(N)\) 表示有序贝尔数，那么总复杂度为 \(\mathcal{O}(N^{N + 1} + a(N) N^3)\)，肆意通过。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
namespace MODINT {
constexpr valueType MOD = 1e9 + 7;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
}// namespace MODINT
using namespace MODINT;
valueType N, ans;
ValueVector A;
namespace MATH {
ValueVector Fact, InvFact;
void init(valueType n) {
Fact.resize(n + 1);
Fact[0] = 1;
for (valueType i = 1; i <= n; ++i)
Fact[i] = mul(Fact[i - 1], i);
InvFact.resize(n + 1);
InvFact[n] = pow(Fact[n], MOD - 2);
for (valueType i = n - 1; i >= 0; --i)
InvFact[i] = mul(InvFact[i + 1], i + 1);
}
valueType C(valueType n, valueType m) {
valueType result = 1;
for (valueType i = 0; i < m; ++i)
Mul(result, (n - i) % MOD);
Mul(result, InvFact[m]);
return result;
}
}// namespace MATH
using MATH::C;
bool check(ValueVector const &rank) {
ValueVector copy(rank.begin(), rank.begin() + N + 1);
std::sort(copy.begin(), copy.end());
for (valueType i = 1; i <= N; ++i)
if (copy[i] - copy[i - 1] > 1)
return false;
return true;
}
valueType length(ValueVector const &rank) {
ValueVector F(N + 1, 0);
valueType result = 0;
for (valueType i = 1; i <= N; ++i)
for (valueType j = 0; j < i; ++j)
if (rank[i] > rank[j])
result = std::max(result, F[i] = std::max(F[i], F[j] + 1));
return result;
}
valueType calc(ValueVector const &rank) {
valueType const M = *std::max_element(rank.begin(), rank.end());
ValueVector limit(M + 1, std::numeric_limits<valueType>::max());
for (valueType i = 1; i <= N; ++i)
limit[rank[i]] = std::min(limit[rank[i]], A[i]);
for (valueType i = M - 1; i >= 0; --i)
limit[i] = std::min(limit[i], limit[i + 1]);
limit[0] = 0;
ValueMatrix F(M + 1, ValueVector(M + 1, 0));
F[0][0] = 1;
for (valueType i = 1; i <= M; ++i) { // 前 i 段
for (valueType j = i; j <= M; ++j) { // 放了 j 种数
for (valueType k = i - 1; k <= j; ++k) {// 前 i - 1 段放了 j 种数
Inc(F[i][j], mul(F[i - 1][k], C(limit[i] - limit[i - 1], j - k)));
}
}
}
return F[M][M];
}
namespace DFS {
ValueVector rank;
void init(valueType n) {
rank.resize(n + 1);
}
void dfs(valueType x) {
if (x > N) {
if (check(rank))
Inc(ans, mul(length(rank), calc(rank)));
return;
}
for (valueType i = 1; i <= N; ++i) {
rank[x] = i;
dfs(x + 1);
}
}
}// namespace DFS
using DFS::dfs;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> N;
MATH::init(N);
DFS::init(N);
A.resize(N + 1);
for (valueType i = 1; i <= N; ++i)
std::cin >> A[i];
dfs(1);
for (valueType i = 1; i <= N; ++i)
Mul(ans, pow(A[i] % MOD, MOD - 2));
std::cout << ans << std::endl;
return 0;
}