自动搬运

查看原文

来自洛谷，原作者为

	CSP_Sept 私が戻ってきたのはね。 もう一度、星の音を聞くためだよ

搬运于2025-08-24 22:45:13，当前版本为作者最后更新于2023-02-18 21:52:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

解法

Solution 1

萌萌签到题，我们考虑到记 $S(i)$ 表示 $F(1),F(2), \ldots ,F(i)$ 的和，发现 $S(i) \equiv i \pmod 2$。

而若干次进行长度为 $len$ 的操作相当于给数列的总和加上若干次 $S(len)$。这样的操作在模 $2$ 域中是等价的。

容易发现，计算出操作前后序列元素和的差，对 $2$ 取模输出即可。

Solution 2

实际上我们有一种更为有趣的做法，定义 $-1$ 次操作，从而将所有操作全部变为若干次 $len = 1$ 的情况。

具体如下：

对于每个 $i$，

• 若 $a_i<b_i$，则相当于在 $[i,i]$ 上进行了 $b_i-a_i$ 次 $len=1$ 的操作；
• 若 $a_i>b_i$，则相当于在 $[i,i]$ 上进行了 $-(a_i-b_i)$ 次 $len=1$ 的操作。

所以这种情况下，操作总长度即为 $\sum_{i=1}^n(a_i-b_i)$。