XORSUM#11837

XORSUM (Розбір)

Автор проблеми:	Hasan Saleh (MathModel)
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Зверніть увагу, що послідовність є циклічною, що означає, що послідовність має форму

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

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

Ми можемо виконати майже все завдання, отримавши довжину циклу. Довжина циклу - це кількість завершених $3$ -цілих сегментів серед інтервалу. Довжина інтервалу становить $r - l + 1$ r-l+1, отже, $цикли = ⌊ \frac{r - l + 1}{3} ⌋$ \displaystyle \text{цикли}=\left \lfloor \frac{r-l+1}{3} \right \rfloor

Ми отримуємо початковий індекс циклу та останній індекс, помічаючи, що цикл починається з першого $a$ в інтервалі послідовності та закінчується останнім $a \oplus b$ a \oplus b в послідовності, окрім цього ми сумуємо залишкові елементи (яких не більше $2$ ), а сума циклу дорівнює $(r - l + 1 - (r - l + 1) mod 3) \times (a + b + a \oplus b)$ (r-l+1-(r-l+1) \bmod 3) \times (a+b+a \oplus b).

Загальна складність $O (1)$ .

Код 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++

Код 2 (Скорочений)

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