题解：P12137 [蓝桥杯 2025 省 B] 装修报价

· · 题解

首先我们注意到，因为符号有加有减，所以将某一项前面的正负号反转其他的都不变就一一对应到了负的这一项，所以除了第一项前面的符号不能翻，每一项的贡献都是 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;
}