考虑 i=1∏nai 的实际意义,相当于一个 m+1 行 n 列的一个矩阵。
矩阵的第一行就是给定的 a 数组,其余每一行就代表一个操作。
一次操作就把一行的后缀全部加 v,答案就是每一列的和的乘积。
考虑设 fi,j 表示现在考虑了前 i 列,已经操作了 j 行的期望。
首先需要计算以前的贡献:fi,j←fi,j+fi−1,j×j×v+fi−1,j×ai。
考虑新添加一行,有 m−j 剩余行可以选择。
虽然这 m−j 行的贡献都是一样的,但是期望的求解还是是需要计算具体的概率的,所以需要讨论。
为了避免算重复,还需要乘以 ni,所以有状态转移方程:
fi,j=fi−1,j×(j×v+ai)+fi−1,j−1×ni×(m−j+1)