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<1000000007$。请输出这个 $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 翻译