XORSUM#11837
Problem Author: | Hasan Saleh (MathModel) |
Prepared by: | Hasan Saleh (MathModel) |
Edited by: | Hasan Saleh (MathModel) |
Notice that the sequence is cyclic, meaning that the sequence is in the form
We can do almost the whole task by getting the cycle length. The cycle length is the number of completed -integer segments among the interval. We've length of the interval is r-l+1, thus \displaystyle \text{cycles}=\left \lfloor \frac{r-l+1}{3} \right \rfloor
We get the cycle start index and last index , by noticing that the cycle starts with first in the sequence interval and last a \oplus b in the sequence other than that we sum the remaining elements (which are at most ) , and the cycle sum is (r-l+1-(r-l+1) \bmod 3) \times (a+b+a \oplus b).
Total Complexity .
Code 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll a,b,l,r;cin>>a>>b>>l>>r;
vector<ll>v={a,b,(a^b)};
ll x=0;ll y=0;
ll ans=0;
r--;l--;
int cnt=0;
for(int i=l;i<l+3;i++){
if(i%3!=0){
ans+=v[i%3];cnt++;
}else{
x=i;
break;
}
}
for(int i=r;i>r-3;i--){
if((i+3)%3!=2){
ans+=v[(i+3)%3];cnt++;
}else{
y=i;
break;
}
}
cout<<ans+((r-l+1-cnt)/3)*(v[0]+v[1]+v[2])<<"\n";
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
}Code 2 (Shorter)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
ll a,b,l,r;cin>>a>>b>>l>>r;
vector<ll>v={a,b,(a^b)};
ll ans=(v[0]+v[1]+v[2])*((r-l+1)/3);
ll rem=(r-l+1)%3;
ll base=(l-1)%3;
for(int i=0;i<rem;i++){
ans+=v[(base+i)%3];
}
cout<<ans<<"\n";
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
}