题解

思路推导

把最终乘积展开。每个位置的因子要么取原值 $a_i$，要么取某一次操作对它贡献的 $v$。把后者按“来自第几次操作”分组；不同操作相互独立。同一次操作若影响了某个较靠前位置，就必然影响其后的所有位置，因此只需关心该组第一次出现的位置。

令 $dp_{i,j}$ 表示已处理乘积的前 $i$ 个因子，展开项中已经使用了 $j$ 个不同操作轮次的贡献总和。处理位置 $i$ 时有两类选择。若取原值或已出现操作的贡献，乘数为 $a_i+jv$；若启用一个新操作轮次，有 $m-j$ 种选择，而随机前缀端点能够影响位置 $i$ 的概率为 $i/n$，乘数为 $(m-j)iv/n$。

因此

$dp_{i,j}\mathrel{+}=dp_{i-1,j}(a_i+jv)$，

$dp_{i,j+1}\mathrel{+}=dp_{i-1,j}(m-j)iv/n$。

答案为 $\sum_j dp_{n,j}$。

做法

子任务 1 枚举全部 $n^m$ 个操作位置序列，逐次修改数组并平均乘积。

子任务 2 维护所有子集乘积的期望。一次随机操作对每个子集作后缀子集变换，重复 $m$ 轮即可，复杂度只适合较小的 $n,m$。

满分算法使用上述“不同操作轮次类别数”动态规划，只保留相邻两行。

正确性证明

乘积展开后的每一项都唯一确定每个位置取原值还是某轮操作贡献。已经出现的 $j$ 个轮次若再次在更靠后位置出现，其贡献必为 $v$，与取原值合并为乘数 $a_i+jv$。若选择此前未出现的轮次，轮次有 $m-j$ 种，而该轮随机选择的起点不超过 $i$ 的概率为 $i/n$；成功时贡献 $v$，故第二类乘数为 $(m-j)iv/n$。

两类转移互斥并覆盖展开式的全部项；不同轮次独立，概率乘积可按首次出现依次计入。由归纳，$dp_{i,j}$ 精确等于对应展开项期望之和，最终对 $j$ 求和即为完整乘积期望。

复杂度分析

满分算法时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。