P8307 〈 TREEのOI 2022 Spring 〉Absolutely Simple Game 题解

· · 题解

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

考虑归纳法

\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$ 的计算式得到 $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 的情况显然符合给出的式子，所以是没有影响的。