自动搬运

查看原文

来自洛谷，原作者为

	SDSXC 打表代替思考，观察代替推导，等等，计数是什么？

搬运于2025-08-24 23:13:02，当前版本为作者最后更新于2025-04-12 16:03:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先我们注意到，因为符号有加有减，所以将某一项前面的正负号反转其他的都不变就一一对应到了负的这一项，所以除了第一项前面的符号不能翻，每一项的贡献都是 $0$。

于是有贡献的只有从第一项开始，中间全填 $\oplus$ 的项。只需要求出对于 $A_{[1,k]}$ 每个构成的这一项，他一共贡献了多少次即可。$A_k$ 与 $A_{k+1}$ 之间必须是加或减，后面的随便填，一共是 $2\times 3^{n-k-1}$ 次，注意最后一项只有 $1$ 的贡献需要特判。预处理 $3$ 的幂次，再结合前缀和就 $O(n)$ 的解决了这个问题。以上就足以通过此题。

虽然时间复杂度到瓶颈了，但是空间上还可以再优化。我们设 $S_k=\bigoplus_{i=1}^k A_i$，只考虑前 $k$ 项时答案为 $Ans_k$，由之前的推导不难发现递推式 $Ans_k=3Ans_{k-1}-S_{k-1}+S_k$。于是就做到了 $O(n)$ 时间，$O(1)$ 空间。

213B，目前最短的 AC 代码。

#include<bits/stdc++.h>
#define ll long long
#define p 1000000007ll
using namespace std;
ll ans=0,sum=0;int n;
int main(){
	cin>>n;for(int i=1,x;i<=n;i++)cin>>x,ans=(ans*3-sum+(sum^=x)+p)%p;cout<<ans;
	return 0;
}