专栏文章

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

llinjinkun
P12137题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhwi8d
此快照首次捕获于
2025/12/02 02:41
3 个月前
此快照最后确认于
2025/12/02 02:41
3 个月前
查看原文
首先异或的优先级最高，所以相当于把所有一段连续的异或值算出来之后，只需考虑加号和减号，那么考虑俩算式：
CPP
...+...
CPP
...-...
设第一个算式前面的东西是 AA，后面的东西是 BB，第二个算式前面的东西是与上同，后面的东西也是与上同，那么两个算式就是： A+BA+B A−BA-B 发现相加后： A+B+(A−B)=2AA+B+(A-B) = 2A BB 被抵消，所以，只有最前面的一段连续异或和有贡献，那么其实对于一个前缀异或，它的贡献就是： prei×2×3n−i−1pre_i \times 2 \times 3^{n-i-1} 因为第 i+1i+1 个位置不能放上 ⊕\oplus，只有两种方案（++ 和 −-），然后后面的 n−i−1n-i-1 个位置 ⊕\oplus、++、−- 都可以随便放，所以是 3n−i−13^{n-i-1}，然后当 i=ni = n 的时候是特殊情况，贡献为 preipre_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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...