「KDOI-06-J」翻转与反转题解

总起

各位大佬们好！
看了楼上的题解，觉得有些~~文字过多~~。

本蒟蒻想介绍一种仅使用初等代数知识的一种做法。

读题发现，这道题主要分为两个部分：

我们可以分别解决这两个问题。

我们记

f(i, j)

表示以

i

为结尾的，下标为

j

的翻转后位置。（注：在这篇题解中，下标从

1

开始）
那么显然：

f(i, j) = i - j + 1

接下来，我们可以尝试“套娃”（更准确的说，我们继续计算

f(i+1, f(i,j))

）

\begin{aligned} f(i+1, f(i,j)) &= f(i+1, i - j + 1)\\ &= (i+1) - (i-j+1) + 1\\ &= j + 1 \end{aligned}

继续“套娃”：

\begin{aligned} f(i+2, f(i+1, f(i,j))) &= f(i+2, j+1)\\ &= (i+2) - (j+1) + 1\\ &= i - j + 2 \end{aligned}

同理，我们可以得出多个这样的式子。
对比：

\begin{aligned} f(i, \dots) &= i - j + 1 \\ f(i+1, \dots) &= j + 1 \\ f(i+2, \dots) &= i - j + 2 \\ f(i+3, \dots) &= j + 2 \end{aligned}

可以总结出：
对于

f(i+v, \dots)

v \bmod 2 = \begin{cases} 0 & f(i+v, \dots) = i - j + v / 2 + 1\\ 1 & f(i+v, \dots) = j + v/2 + 1\text{（整除）} \end{cases}