AT_joig2023_b.絶対階差数列 (Sequence of Absolute Differences)

JOI 高中的葵喜欢对数列进行如下操作：将每一对相邻项的差的绝对值，按顺序组成一个新的数列。

最初，黑板上写有一个长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$。

葵会进行 $N-1$ 次如下操作：

• 假设当前黑板上写有一个长度为 $m$ 的数列 $b_1, b_2, \ldots, b_m$。把这个数列从黑板上擦掉，然后，将长度为 $m-1$ 的新数列 $|b_1-b_2|, |b_2-b_3|, \ldots, |b_{m-1}-b_m|$ 写到黑板上。这里 $|x|$ 表示 $x$ 的绝对值。

在 $N-1$ 次操作之后，黑板上只剩下一个数（长度为 $1$ 的数列）。

给定初始写在黑板上的数列，请编程求出 $N-1$ 次操作后最终黑板上剩下的数。

输入格式如下：

$N\ A_1\ A_2\ \cdots\ A_N$

请输出经过 $N-1$ 次操作后黑板上剩下的那个数。

小题目

1. ($25$ 分) $N=2$。
2. ($75$ 分) 无其他限制。

样例解释 1

一开始，黑板上写着长度为 $4$ 的数列 $3, 1, 4, 1$。

葵将进行 $3$ （$4-1=3$）次操作：

• 第 $1$ 次操作后，黑板上的数列变为 $2, 3, 3$。
• 第 $2$ 次操作后，黑板上的数列变为 $1, 0$。
• 第 $3$ 次操作后，黑板上的数列变为 $1$。

因此最后黑板上剩下的数是 $1$，输出 $1$。

这个输入样例满足小题目 $2$ 的限制。

样例解释 2

这个输入样例满足所有小题目的限制。

样例解释 3

这个输入样例满足小题目 $2$ 的限制。

样例解释 4

这个输入样例满足小题目 $2$ 的限制。

样例解释 5

这个输入样例满足所有小题目的限制。

约束条件

• $2 \leqq N \leqq 2\,000$。
• $0 \leqq A_i \leqq 10^9$。
• 所有输入均为整数。

由 ChatGPT 5 翻译