E

定义f(a),为a中所有不重复的子序列个数

求所有长度为n,字符集大小为m的序列的 Σf(a)

递推

不考虑重复 $res_i = 2mres_{i-1}$ (原来答案和原答案和新加入的字符组成的答案
重复部分出现次数恰好为 $res_{i-1} - emp_{i-1}$ $emp_i = m^i$ 为空序列
(考虑分别去掉最后一个字符的前一个字符后与最后一个字符组成的新序列,恰好为原来序列的个数
注意空不考虑空序列

最后递推式为
$res_i = (2m-1)res_{i-1} + m^{i-1} , res_0 = 1$

F

长度为n的序列ai
选取一段连续的子序列,从位置j开始,长度为m (j,m任意)
使得 $sum_{k=1}^m ka[j+k]$ 最大

斜率优化

定义 sum[i] 为前缀和,mul[i] 为 $sum_j=1^i ja[i]$
d[i] 为以位置i结束的最优答案

$d[i] = max(mul[i] - mul[j] - j(sum[i] - sum[j]))$ (j = 0,..,i-1)

这个式子可以斜率优化
$x(j) = j,y(j) = jsum[j] - mul[j],k = sum[i]$

x单调递增,k不单调
维护一个斜率单调递减的凸壳,二分更新答案即可