[NOIP2020] 微信步数
为什么有一个 \(80pts\) 和 \(100pts\) 毫无关系？？
80pts：\(w \le 10^6\)
想法很简单，因为每一维都是独立的，对于第 \(i\) 维的第 \(j\) 个格子计算出它什么时候“出局”，记作 \(t_{i, j}\)。
那么对于初始位置，答案就是 \(\min(t_{1, a_1}, t_{2, a_2}, \dots, t_{k, a_k})\)
按 \(t\) 从大到小排序（基数排序），枚举这个最小值计算答案。
时间复杂度：\(nk + \sum w\)
100pts
换一个角度，不要计算每个格子什么时候出局，计算对于时刻 \(t\) 还有多少格子没有出局，求和即为答案。
每一维还是独立的。对于每一维，先考虑第一轮，设 \(l_{i, j}, r_{i, j}\) 表示第 \(i\) 步后第 \(j\) 维的最小位移/最大位移，则只有 \([-l_{i, j} + 1, r_{i, j}]\) 没有出局，这一维有 \(w_j - r_{i, j} + l_{i, j}\) 的取值，乘起来即可。（\(80pts\) 的 \(t_{i, j}\) 也是利用这个加上双指针可以直接计算。）
设走完一轮后第 \(j\) 维的最终位移为 \(s_j\)，则第二轮中第 \(i\) 步后第 \(j\) 维有 \([-\min(l_{n, j}, s_j + l_{i, j}) + 1, \max(r_{n, j}, s_j + r_{i, j})]\)，后面的都是这种形式，设第二轮有 \(p_{i, j}\) 种取值，则第 \(c\) 轮有 \(p_{i, j} - (c - 1)|s_j|\) 种。
于是第一轮单独处理后，计算每一轮第 \(i\) 步结束后的答案就是（\(R_i\) 是轮数最大值，即第 \(R_i + 1\) 轮有的维没有取值了）：
\(R_i\) 可以很大，可以看成未知数，其他看成参数。注意到后面一坨其实是 \(k\) 个关于 \(c\) 的一次函数相乘，然后求和。整个式子是 \(k + 1\) 次多项式，可以直接由拉插得到答案。
时间复杂度：\(O(nk^2)\)。
总结
这个题虽然最开始 \(80pts\) 看起来很高，其实没有前途，因为无法避免求 \(t_{i, j}\)。
换一个角度思考：对于每个时刻计算贡献。得到 \(S_i\) 后要机敏的发现可以用拉插维护，因为整个式子中只有 \(R_i\) 很大，其他都很小。拉插正是将一个很难求的 \(f(n)\) 转化为 \(k + 1\) 个好求的 \(f(x_i)\)。