有点神仙的 dp

相当于求

\[\sum_{i=1}^n\sum_{j=i}^ncalc(i,j) \]

看到这个熟悉的形式我们理所当然的应该去想分治……

但是这个题不是这样。我们首先考虑如何去求 \(calc(i,j)\)。有一个比较显然的贪心就是倒着考虑，每遇到一个 \(a_i > a_{i+1}\) 我们即可考虑拆掉 \(a_i\)。可以知道对于上面一对相邻的数可以被拆出 \(k=\lceil\frac{a_i}{a_{i+1}}\rceil\) 项，要求第一项最大则是 \(\lfloor\frac{a_i}{k}\rfloor\)。这样的话我们得到了一个 \(O(n^2)\) 的贪心。

我们考虑如何去优化这个贪心

设 \(dp_{i,x}\) 表示以 \(\rm i\) 为左端点的所有子序列的起始元素是 \(\rm x\) 的方案数

这个方程的状态是 \(O(n\sqrt n)\) 的，根据整除分块理论显然。对于最后答案我们考虑以贡献的形式来维护，具体来说对于一个 \(dp_{i,x}\) 它向答案贡献 \(i\times dp_{i,x} \times k\)，\(k\) 的意义同上。

说实话前面这个贪心不是关键，重要的是这个把贪心过程优化为计数问题算贡献这一步，可以说是充满了仙气。

link

有点卡常一开始用 unordered_map 还过不去，最后还是用 vector 迭代才过去的