其实不难,带点思维,数学题。
不会用md语法,所以每次只好把解释全写进注释T_T
/*
题意:给你n个数,让你向这n个数里面填运算符(^ + -),最后求出每一种填法的运算结果的和
*/
/*
一开始拿到不一定有头绪,那么就先想暴力,毕竟是蓝桥杯,数据范围有一个N<=13的,这个明显就是让你打暴力的,
暴力的话就是暴搜了,三个运算符,复杂度就是 O(3^n) 13的话正好不超时。显然这个是不能当正解的。
但是我们可以惊奇的发现题目中样例给出来的解释,后面有好多都抵消了,
ans=7 s=0^2^5 res=7
ans=14 s=0^2+5 res=7
ans=11 s=0^2-5 res=-3
ans=16 s=0+2^5 res=5
ans=23 s=0+2+5 res=7
ans=20 s=0+2-5 res=-3
ans=15 s=0-2^5 res=-5
ans=18 s=0-2+5 res=3
ans=11 s=0-2-5 res=-7
我们可以发现,后面那么多项数大部分都抵消了,
也就是说当从前往后出现第一个加号或者减号的时候那后面的数就都不用算了,
因为必定还有有一个和他相反的把后面抵消掉。
那么也就是说,我们只需要找到每个前缀异或的分界位置,然后乘上他们的数量就可以算出来了。
前缀异或和直接用一个数组搞定,现在问题转换成数量怎么求,
这个直接可以用组合数来算,
比如前缀只有一个数,那么他第二个位置存放的符号就有+ - 两种,
之后的n-2个位置有三种方法,那么数量就是 2*(3^(n-2))
前缀有两个数的话,下一个位置依旧是+ - 两种,后面还剩下n-3个位置任选,所以就是 2*(3^(n-3)) ,
依次类推,知道 n-k为0 ,然后还需要特判一下第一个,即可求出
千万注意: 异或和不要取模,因为取模完数就变了,后面再异或也会炸,所以要保留,反正异或操作也不会爆LL
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9,p=1e9+7;
int a[N],n,pre[N],ans;
int qmi(int a,int b) //快速幂
{
int res=1LL;
while(b){
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res%p;
}
void solve(){
for(int i=1;i<=n;++i) //前缀异或和
pre[i]=(pre[i-1]^a[i]);
ans=0LL;
for(int mi=n-2,pos=1;mi>=0;--mi,++pos)//直接计算
ans=(ans+2*qmi(3,mi)%p*pre[pos]%p)%p;
ans=(ans+pre[n])%p;
cout<<ans%p<<'\n';
}
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
solve();
return 0;
}