X

讲课的时候偶然发现的一道题。其他题解好麻烦啊！ 首先思考:数轴上有一堆点上站着人。他们走到哪个点的路程和是最小的呢？ 我们可以通过许多方法证明，应当取中位数。所以我们一定是想走到中央。 我们考虑，走 $\leq$ 一步就能到中央的格子数目是 $9$，而走 $\leq$ 两步就能到中央的格子数是 $21$。 但其实，走两步到中心点其实就是走一步到距离中心 $=$ 一步的 $8$ 个点再走一步而已。 据此我们可以 DP。设 $f_i$ 表示走 $\leqslant i$ 步就能到中心点的点数，那么 $f_0=0$。 $$ f_i=f_{i-1}+((2\times i+1)\times 4-4)\times i $$ 答案最后就是 $f_{\lfloor\frac{n}{2}\rfloor}$。 但其实展开就可以发现，答案就是自然数平方和的 $8$ 倍的第 ${\lfloor\frac{n}{2}\rfloor}$ 项。所以答案应该是： $$ \dfrac{{\lfloor\frac{n}{2}\rfloor}\times({\lfloor\frac{n}{2}\rfloor}+1)\times (2\times {\lfloor\frac{n}{2}\rfloor})+1}{6} $$ 复杂度 $O(T)$ 而不是 $O(n+T)$。 为了防止爆 `long long` 可以写成 `ans = 1ll * (m + 1) * m / 2ll * (2ll * m + 1) / 3 ;`