XORSUM#11837
Iniciar sesión

XORSUM (Editorial)

Autor del problema:

Hasan Saleh (MathModel)

Preparado por:

Hasan Saleh (MathModel)

Editado por:

Hasan Saleh (MathModel)

Observa que la secuencia es cíclica, lo que significa que la secuencia tiene la forma

[a,b,a \oplus b,a,b,a \oplus b,....]

Podemos realizar casi toda la tarea obteniendo la longitud del ciclo. La longitud del ciclo es el número de segmentos de enteros completados entre el intervalo. La longitud del intervalo es r-l+1, por lo tanto \displaystyle \text{ciclos}=\left \lfloor \frac{r-l+1}{3} \right \rfloor

Obtenemos el índice de inicio del ciclo y el índice final, al notar que el ciclo comienza con el primer en el intervalo de la secuencia y termina con el último a \oplus b en la secuencia, además de que sumamos los elementos restantes (que son como máximo ), y la suma del ciclo es (r-l+1-(r-l+1) \bmod 3) \times (a+b+a \oplus b).

Complejidad total .

Código 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;
}
C++

Código 2 (Más corto)

#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;
}
C++