题解：P12137 [蓝桥杯 2025 省 B] 装修报价
linjinkun
·
·
题解
首先异或的优先级最高，所以相当于把所有一段连续的异或值算出来之后，只需考虑加号和减号，那么考虑俩算式：
...+...
...-...
设第一个算式前面的东西是 A，后面的东西是 B，第二个算式前面的东西是与上同，后面的东西也是与上同，那么两个算式就是：
A+B
A-B
发现相加后：
A+B+(A-B) = 2A
$$pre_i \times 2 \times 3^{n-i-1}$$
因为第 $i+1$ 个位置不能放上 $\oplus$，只有两种方案（$+$ 和 $-$），然后后面的 $n-i-1$ 个位置 $\oplus$、$+$、$-$ 都可以随便放，所以是 $3^{n-i-1}$，然后当 $i = n$ 的时候是特殊情况，贡献为 $pre_i$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int N = 1e5+5;
int po[N],a[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
po[0] = 1;
for(int i = 1;i<=n;i++)
{
cin >> a[i];
if(i<=n-2)
{
po[i] = 3ll*po[i-1]%mod;
}
}
long long pre = 0,ans = 0;
for(int i = 1;i<=n;i++)
{
pre^=a[i];
if(i<n)
{
ans = (ans+2*pre%mod*po[n-i-1]%mod);
}
else
{
ans = (ans+pre)%mod;
}
}
cout << ans;
return 0;
}
```