XORSUM#11837
Se connecter

XORSUM (Corrigé)

Auteur du problème:

Hasan Saleh (MathModel)

Préparé par:

Hasan Saleh (MathModel)

Édité par:

Hasan Saleh (MathModel)

Remarquez que la séquence est cyclique, ce qui signifie que la séquence est sous la forme

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

Nous pouvons faire presque toute la tâche en obtenant la longueur du cycle. La longueur du cycle est le nombre de segments d'entiers complétés parmi l'intervalle. La longueur de l'intervalle est r-l+1, donc \displaystyle \text{cycles}=\left \lfloor \frac{r-l+1}{3} \right \rfloor

Nous obtenons l'index de début du cycle et l'index de fin, en remarquant que le cycle commence par le premier dans l'intervalle de séquence et se termine par le dernier a \oplus b dans la séquence, en dehors de cela nous additionnons les éléments restants (qui sont au maximum ), et la somme du cycle est (r-l+1-(r-l+1) \bmod 3) \times (a+b+a \oplus b).

Complexité totale .

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

Code 2 (Plus court)

#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++