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

题目描述

老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系统，只需用户提供 $N$ 项装修相关费用 $A_1,A_2,\dots ,A_N$，系统便会根据这些费用生成最终的报价。

然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只会给出一个最终报价，而不会公开任何运算过程或中间步骤。

公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插入 $+$（加法）、$-$（减法）或 $\oplus$（异或）运算符，并按照特定优先级规则计算结果：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以及中间过程都不会对外公开。

为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的运算符组合，计算出所有可能出现的结果的总和。如果最终报价明显超出这个范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇为吃力，便向你求助。

现在，请你帮老王算出所有可能的结果的总和。由于该总和可能很大，你只需提供其对 $10^9+7$ 取余后的结果即可。

输入格式

第一行输入一个整数 $N$，表示装修相关费用的项数。

第二行输入 $N$ 个非负整数 $A_1,A_2,\dots ,A_N$，表示各项费用。

输出格式

输出一个整数，表示所有可能的总和对 $10^9+7$ 取余后的结果。

输入输出样例 #1

输入 #1

3
0 2 5

输出 #1

11

说明/提示

对于输入样例中的三个数 $A=[0,2,5]$，所有可能的运算符组合共有 $9$ 种。计算结果如下：

$$0\oplus 2\oplus 5=7$$
$$0\oplus 2+5=7$$
$$0\oplus 2-5=-3$$
$$0+2\oplus 5=7$$
$$0+2+5=7$$
$$0+2-5=-3$$
$$0-2\oplus 5=-7$$
$$0-2+5=3$$
$$0-2-5=-7$$

所有结果的总和为：

$$7+7+(-3)+7+7+(-3)+(-7)+3+(-7)=11$$

$11$ 对 $10^9+7$ 取余后的值依然为 $11$，因此，输出结果为 $11$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1\le N\le 13$，$0\le A_i\le 10^3$。
• 对于 $60\%$ 的评测用例，$1\le N\le 10^3$，$0\le A_i\le 10^5$。
• 对于 $100\%$ 的评测用例，$1\le N\le 10^5$，$0\le A_i\le 10^9$。

C++实现

#include<bits/stdc++.h>
using namespace std;
using ll=long long; 
const ll m=1e9+7;
ll n,fare[100005],ans;
ll pre[100005],cnt[100005];//分别记录异或前缀,贡献数量
ll quike(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1){
			ans=(ans*a)%m;//必须边乘边取模,否则会溢出!
		}
		a=(a*a)%m;
		b>>=1;
	}
	return ans;
}

int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>fare[i];
	}
	for(ll i=1;i<=n;i++){
		pre[i]=pre[i-1]^fare[i];
		if(i<n){
			cnt[i]=2*quike(3,n-i-1);//不能直接用`pow(a,b)` 函数,否则会溢出!
		}else{
			cnt[i]=1;
		}
	}
	for(ll i=1;i<=n;i++){
		ans = (ans + pre[i] * cnt[i]) % m;
	}
	cout<<ans;
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容