AT_arc104_e [ARC104E] Random LIS

给定一个长度为 $N$ 的整数序列 $A_1,\ A_2,\ \cdots,\ A_N$。 同样长度为 $N$ 的整数序列 $X$，对于每个 $i\ (1\leq i\leq N)$，$X_i$ 独立且等概率地从满足 $1\leq X_i\leq A_i$ 的整数中随机选取。 此时，请计算 $X$ 的最长严格递增子序列长度的期望值，并对 $1000000007$ 取模输出。 更准确地说，期望值可以表示为一个既约分数 $\frac{P}{Q}$，并且根据本题的约束，可以证明存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{1000000007}$，且 $0\leq R

输入通过标准输入按以下格式给出。 > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

请输出期望值对 $1000000007$ 取模后的结果。

## 注释 序列 $X$ 的子序列指的是从 $X$ 中按原顺序取出若干元素所形成的序列。$X$ 的最长递增子序列指的是 $X$ 的所有严格递增子序列中长度最大的一个。 ## 约束 - $1\leq N\leq 6$ - $1\leq A_i\leq 10^9$ - 输入均为整数 ## 样例解释 1 $X$ 共有 $6$ 种可能，概率均为 $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 $X$ 共有 $4$ 种可能，概率均为 $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$。 由 ChatGPT 4.1 翻译