ANIG
对于序列 \(\{a_n\}\),每次随机选择 \(i\) 令 \(a_i\gets a_i+1\)，求 \(a\) 前缀和数组的积的期望。
转化一下，先对 \(a\) 做一下前缀和，假设最后第 \(i\) 个位置变成了 \(a_i+b_i\)，答案即为 \(\prod (a_i+b_i)\)，这里考虑一个组合意义，将 \(b_i\) 看成和覆盖它的一个操作匹配，这样设 \(f_{n,m}\) 为 dp 到第 \(n\) 个数，前面所有数匹配的操作的集合大小为 \(m\) 的方案，那么对于 \(n\)，要么选择 \(a_i\)，要么匹配前面点匹配过的一个操作，要么匹配一个前面没有匹配的操作，\(O(n^2)\) 转移即可。
对于序列 \(\{a_n\}\),每次带权随机以 \(\frac{b_i}{\sum\limits_j b_j}\) 的概率将 \([i,i+m-1]\) 的 \(a_i\) 加一，求 \(a\) 积的期望。
沿用上述组合意义转化，考虑一个点集 \(S\) 全都匹配到操作 \(x\)，那么其贡献只和 \(S\) 的最左边和最右边的点有关，于是设 \(f_{n,m,S}\) 表示 dp 到第 \(n\) 个数，匹配集合的大小为 \(m\)，前面 \([n-m,n]\) 的点是否被钦定为左端点并且还没有决定右端点的状态为 \(S\)，dp 转移也是容易的。复杂度 \(O(n^2m2^m)\)。
这个对 \(m>n/3\) 有另一种将序列划分为三块同时 dp，可以 \(O(n^6)\)。
NineSuns
当决策单调性 dp 需要莫队计算 \(w(l,r)\)，且 \(f_i\) 从 \(f_j(j<i)\) 转移时的 \(O(n\log n)\) 做法。
设 \(p_i\) 表示 \(i\) 的最优决策点。
考虑分治，当分治到区间 \([l,r]\) 时，要求 \([0,l]\) 的 \(f,p\) 都计算正确，计算结束后 \([l,r]\) 的 \(p,f\) 都正确。
\(r\) 在只考虑 \([0,l]\) 的转移时 \(f,p\) 正确，由于决策单调性，故在只考虑 \([0,l]\) 时 \(p_l\le p_{mid}\le p_r\)，求出 \(p_mid\)，然后递归到 \([l,mid]\)，然后用 \([l+1,mid]\) 的值更新 \(r\)，递归到 \([mid,r]\)。
不难验证上述分治过程满足条件。在处理 \([p,p+1]\) 直接返回即可。
对于每一层，指针移动量是 \(O(n)\) 的，于是可以 \(O(nk\log n)\) 的复杂度处理，其中 \(k\) 是由 \(w(l,r)\) 的 \(l,r\) 指针移动 \(1\) 后计算新 \(w(l‘,r’)\) 的复杂度。