自动搬运

查看原文

来自洛谷，原作者为

	Remake_ **

搬运于2025-08-24 22:37:52，当前版本为作者最后更新于2022-05-01 11:16:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

很多人想要一个证明，那我就直接借用这篇题解通过打表获得的式子了。

考虑归纳法

$$ a_n=\left\{ \begin{aligned} \frac{n-1}{2}(n\operatorname{mod} 4=1) \\ \frac{n}{2}(n\operatorname{mod}2=0) \\ \frac{n+1}{2}(n\operatorname{mod}4=3) \end{aligned} \right. $$

不妨假设此条件对于 $a_1\sim a_{n-1}$ 均成立。

很显然我们可以将其改写成 $a_n=\frac{n-[n\operatorname{mod}4=1]+[n\operatorname{mod}4=3]}{2}$。

$a_n$ 的计算式是 $n-1-\min\limits_{i=1}^na_{i-1}+a_{n-i}$。

我们将我们所改写的代回到 $a_n$ 的计算式得到 $a_n=n-1-\min\limits_{i=1}^n\frac{n-1+[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]}{2}$。

里面的 $\frac{n-1}{2}$ 可以提出来，变成了 $a_n=\frac{n-1}{2}-\min\limits_{i=1}^n\frac{[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]}{2}$。

那么现在我们所需要求的就变成了对于给定 $n$，求 $\min\limits_{i=1}^n[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]$。

分类讨论即可。

$n\operatorname{mod}4=0$:

1.$(i-1)\operatorname{mod}4=0$，则 $(n-i)\operatorname{mod}4=3$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=1$。

2.$(i-1)\operatorname{mod}4=1$，则 $(n-i)\operatorname{mod}4=2$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-1$。

3.$(i-1)\operatorname{mod}4=2$，则 $(n-i)\operatorname{mod}4=1$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-1$。

4.$(i-1)\operatorname{mod}4=3$，则 $(n-i)\operatorname{mod}4=0$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=1$。

不难发现此时 $\min\limits_{i=1}^n[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-1$。

回代之后可得，若 $n\operatorname{mod}4=0$，则 $a_n=\frac{n}{2}$。

$n\operatorname{mod}4=1$:

1.$(i-1)\operatorname{mod}4=0$，则 $(n-i)\operatorname{mod}4=0$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=0$。

2.$(i-1)\operatorname{mod}4=1$，则 $(n-i)\operatorname{mod}4=3$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=0$。

3.$(i-1)\operatorname{mod}4=2$，则 $(n-i)\operatorname{mod}4=2$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=0$。

4.$(i-1)\operatorname{mod}4=3$，则 $(n-i)\operatorname{mod}4=1$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=0$。

不难发现此时 $\min\limits_{i=1}^n[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=0$。

回代之后可得，若 $n\operatorname{mod}4=1$，则 $a_n=\frac{n-1}{2}$。

$n\operatorname{mod}4=2$:

1.$(i-1)\operatorname{mod}4=0$，则 $(n-i)\operatorname{mod}4=1$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-1$。

2.$(i-1)\operatorname{mod}4=1$，则 $(n-i)\operatorname{mod}4=0$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-1$。

3.$(i-1)\operatorname{mod}4=2$，则 $(n-i)\operatorname{mod}4=3$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=1$。

4.$(i-1)\operatorname{mod}4=3$，则 $(n-i)\operatorname{mod}4=2$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=1$。

不难发现此时 $\min\limits_{i=1}^n[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-1$。

回代之后可得，若 $n\operatorname{mod}4=2$，则 $a_n=\frac{n}{2}$。

$n\operatorname{mod}4=3$:

1.$(i-1)\operatorname{mod}4=0$，则 $(n-i)\operatorname{mod}4=2$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=0$。

2.$(i-1)\operatorname{mod}4=1$，则 $(n-i)\operatorname{mod}4=1$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-2$。

3.$(i-1)\operatorname{mod}4=2$，则 $(n-i)\operatorname{mod}4=0$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=0$。

4.$(i-1)\operatorname{mod}4=3$，则 $(n-i)\operatorname{mod}4=3$，此时 $[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=2$。

不难发现此时 $\min\limits_{i=1}^n[(i-1)\operatorname{mod}4=3]-[(i-1)\operatorname{mod}4=1]-[(n-i)\operatorname{mod}4=1]+[(n-i)\operatorname{mod}4=3]=-2$

回代之后可得，若 $n\operatorname{mod}4=3$，则 $a_n=\frac{n+1}{2}$。

完了。

当然这个东西有一个前提，就是 $(i-1)\operatorname{mod}4=0,1,2,3$ 均能取到。

所以说这个东西对 $n<4$ 是不适用的。

但是我们发现 $n<4$ 的情况显然符合给出的式子，所以是没有影响的。