菜王的 blog

神仙题，不愧是 *3500。参考了官方题解以及 $\mathrm{B\color{red}{enq}}$ 的代码。感觉有些地方思维跳跃有点严重，括号标记出来了。

我们先考虑二维的情况（出题人怕不是出了个二维的又加强成四维的吧）。考虑一个点 $(a, b)$ 是否可以用恰好 $k$ 步到达。显然以下两个条件是到达的必要条件：

1. $|a| + |b| \equiv 1 + 2 + \dots + k \pmod 2$，因为无论如何移动都不影响距离的奇偶性。
2. $|a| + |b| \le 1 + 2 + \dots + k$，否则次数不够。

我们猜想这也是充分条件（什么经典猜结论），尝试证明。$k \le 2$ 的情况是平凡的，考虑 $k > 2$ 时归纳证明。

如果 $|a| + |b - k| \le 1 + 2 + \dots + k - 1$，则结论成立。考虑反证，假设 $|a| + |b - k| > 1 + 2 + \dots + k-1$。如果 $b \ge k$，可以导出矛盾 $|a| + |b| - k \le (1 + 2 + \dots + k) - k$。如果 $b < k$，可以导出矛盾 $|a| + k - |b| \le k \le 1 + 2 + \dots + k - 1$，于是结论成立。

接下来我们回到四维的情况。尝试将刚才的结论推广到四维，但是实际上这不成立。比如说，$f(0, 1, 1, 1) = 5$ 而不是 $2$。但是，我们猜测这个结论的反例比较少（这怎么看出来的啊？），而我们可以直接处理。

根据猜测，我们定义 $S_k$ 为满足结论，但是恰好 $k$ 步无法走到的位置集合，而 $S_k$ 的大小不会很大。

考虑求出所有的 $S_k$。类似前面的结论，我们可以得到另一个结论：假设 $(a, b, c, d) \in S_k$（令 $0 \le a \le b \le c \le d$），要么有 $k \le 6$，要么有 $(a, b, c, d - k) \in S_{k - 1}$。

换句话说，对于 $k > 6$ 的情况，$S_k$ 中的备选元素可以在 $S_{k-1}$ 的基础上移动一步得到，又因为我们知道了 $S_{k-1}$，所以我们根据其定义可以 $O(1)$ 判断被选元素是否真的不可达。也就是说，$S_k$ 可以快速生成。

现在我们来证明结论。与上一个结论类似的，如果 $a + b + c + |d - k| \le 1 + 2 + \dots + k - 1$，则结论成立。考虑反证，假设 $a + b + c + |d - k| > 1 + 2 + \dots + k-1$。如果 $d \ge k$，可以导出矛盾 $a + b + c + d - k \le (1 + 2 + \dots + k) - k$。如果 $d < k$，可以导出矛盾 $a + b + c + k - d \le a + b + k \le 3k - 2\le 1 + 2 + \dots + k - 1$（$k \ge 7$ 时成立），于是结论成立。

现在 $S_k$ 已经很好求了：

• 对于 $k \le 6$，暴搜走 $k$ 步能到达的地方，并暴力枚举每个符合定义的位置加入 $S_k$。
• 对于 $k > 6$，按照前文所述从 $S_{k-1}$ 的基础上求出候选集合 $O(1)$ check 即可。

光是这样还无法通过，状态太多了。因为每一维本质相同且正负没有影响，所以我们只需保留所有的 $0 \le a \le b \le c \le d \le 10^3$ 的位置 $(a, b, c, d)$，最后再重新排列它们即可，$|S_k|$ 就可以控制在 $5 \times 10^3$ 以下。

最后的计数是简单的。我们先把所有点以错误结论得到的答案计算，设 $f_i$ 表示距离原点的距离为 $i$ 的位置数，$g_i$ 为最小的（对于距原点为 $i$ 的点同时满足两个充要条件的）移动次数 $k$。$f_i$ 可以用一个背包 dp 来求，而 $g_i$ 可以直接暴力求，则 $\sum f_i g_i$ 就是初始答案。

算错次数的点一定在 $S$ 中出现过，所以我们可以从小到大扫，暴力更新这些点的答案。具体细节见代码。