分数: 700 点
问题陈述
给定的是长度的整数序列 N: A_1, A_2, \cdots, A_N.
整数序列 X,其长度也是 N,将通过独立选择的方式随机选择 X_i 来自整数的均匀分布 1, 2, \ldots, A_i 对于每个 i (1 \leq i \leq N).
计算该序列的最长递增子序列的长度期望值 X,模数 1000000007.
更正式地说,在问题的约束下,我们可以证明期望值可以表示为有理数,即不可约分数 \frac{P}{Q},并且唯一存在一个整数 R 这样 R \times Q \equiv P \pmod {1000000007} 和 0 \leq R < 1000000007,所以打印这个整数 R.
注释
序列的子序列 X 是通过提取部分元素得到的序列 X 并在不改变顺序的情况下排列它们。序列的最长递增子序列 X 是严格递增子序列中长度最大的序列 X.
约束
- 1 \leq N \leq 6
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印期望值模 1000000007.
示例输入 1
3 1 2 3
示例输出 1
2
X 成为以下之一,有概率 1/6 对于每个:
- X = (1,1,1),其中最长递增子序列的长度为 1;
- X = (1,1,2),其中最长递增子序列的长度为 2;
- X = (1,1,3),其中最长递增子序列的长度为 2;
- X = (1,2,1),其中最长递增子序列的长度为 2;
- X = (1,2,2),其中最长递增子序列的长度为 2;
- X = (1,2,3),其中最长递增子序列的长度为 3.
因此,最长递增子序列的长度期望值为 (1 + 2 + 2 + 2 + 2 + 3) / 6 \equiv 2 \pmod {1000000007}.
示例输入 2
3 2 1 2
示例输出 2
500000005
X 成为以下之一,有概率 1/4 对于每个:
- X = (1,1,1),其中最长递增子序列的长度为 1;
- X = (1,1,2),其中最长递增子序列的长度为 2;
- X = (2,1,1),其中最长递增子序列的长度为 1;
- X = (2,1,2),其中最长递增子序列的长度为 2.
因此,最长递增子序列的长度期望值为 (1 + 2 + 1 + 2) / 4 = 3 / 2。自从 2 \times 500000005 \equiv 3 \pmod {1000000007},我们应该打印 500000005.
示例输入 3
6 8 6 5 10 9 14
示例输出 3
959563502