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

· · 题解

思路

注意题目求的是每种情况的和。

再观察题目不难可以发现 + 和 - 是可以抵消的。

枚举一下样例不难发现规律。

5+2+0
5-2-0
5+2-0
5-2+0
5+2^0
5-2^0
5^2+0
5^2-0
5^2^0

再用一个前缀异或维护即可。

另外，膜拜掰掰手指大佬。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int res = 0,f = 1;
    char ch = getchar();
    while (ch<'0'||ch>'9') f = (ch=='-'?-f:f),ch = getchar();
    while (ch>='0'&&ch<='9') res = (res<<3)+(res<<1)+(ch^48),ch = getchar();
    return res*f;
}
void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x>9) write(x/10);
    putchar(x%10+'0');
}
void writech(int x,char ch){write(x),putchar(ch);}
const int N = 1e5+5,MOD = 1e9+7;
int n;
int a[N];
int p3[N];
signed main()
{
    n=read();
    for (int i = 1; i <= n; i++) a[i]=read();
    p3[0]=1;
    for (int i = 1; i <= n; i++) p3[i]=p3[i-1]*3%MOD;
//  掰掰手指
    int ans = 0,sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum^=a[i];
        ans+=sum*(p3[n-i-1]*2)%MOD;
        ans%=MOD;
    }
    ans=(ans+sum)%MOD;
    write(ans);
    return 0;
}
/*
5+2+0
5-2-0
5+2-0
5-2+0
5+2^0
5-2^0
5^2+0
5^2-0
5^2^0

*/