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

Ay2024_4202yA · 2026-01-08 21:18:29 · 题解

思路

题目中有加、减和异或三种运算。
注意到除去开头的数，后面的加减符号换一下两者相加会抵消很多东西。
假设我们把开头 k 个数异或起来，那么后面的 n-k 个数的之间的符号随便改，不难发现任意一种情况都可以构造出跟它相减将后面的 n-k 个数抵消的情况。
所以我们枚举 k，那么从第 k+1 个数开始，每一个数跟它后面的数之间的符号随意改变，对于固定的 k，这些式子相加的和就是填符号的情况数量乘上前面 k 个数的异或值，也就是 \oplus^{k}_{i=1} a_i \times 3^{n-k}。
吗？
注意到，第 k 位和第 k+1 位之间不能填异或符号，不然就变成下一种情况了。
所以这一位只有加减两种情况。
所以对于固定的 k，答案应该是 \oplus^{k}_{i=1} a_i\times 3^{n-k-1} \times 2。
注意，当 k = n 时答案是 n 个数的异或值，且只有一种情况。
还有随时注意取模！

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5,mod=1e9+7;
int n,a[maxn],p3[maxn];
signed main(){
    int n;cin>>n;p3[0]=1;
    for(int i=1;i<=n;i++)p3[i]=p3[i-1]*3%mod;
    for(int i=1;i<=n;i++)cin>>a[i];
    int xr=0,ans=0;
    for(int i=1;i<n;i++){
        xr^=a[i];ans=(ans+xr*p3[n-i-1]%mod*2%mod)%mod;
    }
    xr^=a[n];ans=(ans+xr)%mod;
    cout<<ans<<endl;
    return 0;
}