考虑 i=1nai\prod\limits_{i=1}^n a_i 的实际意义,相当于一个 m+1m+1nn 列的一个矩阵。

矩阵的第一行就是给定的 aa 数组,其余每一行就代表一个操作。

一次操作就把一行的后缀全部加 vv,答案就是每一列的和的乘积。

考虑设 fi,jf_{i,j} 表示现在考虑了前 ii 列,已经操作了 jj 行的期望。

首先需要计算以前的贡献:fi,jfi,j+fi1,j×j×v+fi1,j×aif_{i,j}\gets f_{i,j}+f_{i-1,j}\times j\times v+f_{i-1,j}\times a_i

考虑新添加一行,有 mjm-j 剩余行可以选择。

虽然这 mjm-j 行的贡献都是一样的,但是期望的求解还是是需要计算具体的概率的,所以需要讨论。

为了避免算重复,还需要乘以 in\dfrac{i}{n},所以有状态转移方程:

fi,j=fi1,j×(j×v+ai)+fi1,j1×in×(mj+1)f_{i,j}=f_{i-1,j}\times(j\times v+a_i)+f_{i-1,j-1}\times \dfrac{i}{n}\times (m-j+1)