Каосар і Трійки (Розбір)

Рішення 1 : \mathcal{O}(\log(r-l+1)) блоки

Ми хочемо порахувати невпорядковані трійки \{a,b,c\} з l \le a,b,c \le r і

Але зауважте, що три рівняння насправді є однією і тією ж умовою: якщо a \oplus b = c, то

і аналогічно b \oplus c = a. Отже, вся проблема полягає в тому, щоб порахувати трійки (a,b,c) з c = a \oplus b і всі вони лежать в [l,r]. Також, якщо a=b, то c=0, що є $<l$ (оскільки l \ge 1), тому жодна дійсна трійка не має рівних елементів; те ж саме для a=c або b=c. Отже, кожна дійсна трійка має три різні числа.

Прямий \mathcal{O}((r-l+1)^2) по всіх парах $(a,b)$ неможливий, оскільки $r$ може бути до 10^{18}. Трюк для xor на інтервалі полягає в тому, щоб розділити [l,r] на \mathcal{O}(\log(r-l+1)) блоків (блоки степеня двійки), які вирівняні.

Конкретно, ми робимо відоме розкладання: починаючи з x=l, кожного разу беремо найбільший сегмент степеня двійки, що починається з $x$, який не перевищує $r$ і вирівняний за його довжиною, додаємо його до списку і переміщаємо $x$ вперед. Це дає набір

де кожне L_t є степенем двійки, і s_t \equiv 0 \pmod{L_t}. Кількість таких блоків є \mathcal{O}(\log(r-l+1)).

Тепер візьмемо два таких блоки

з L=2^i і M=2^j. Існує стандартна властивість для цих вирівняних блоків: якщо H = \max(L,M) і k = \log_2 H, тоді набір

є точно одним вирівняним блоком

Більше того (це ключовий факт підрахунку): кожне число $c$ в цьому блоці $C$ має точно \min(L,M) пар прообразів $(a,b)$ з a \in A, b \in B і a \oplus b = c. Інтуїтивно: більший блок (той, що має розмір $H$) визначає всю форму xor-образу, а менший блок просто говорить вам, скільки способів ви можете потрапити на кожне конкретне значення xor. Це точно та властивість, яку ви отримуєте з конкретного діадичного розкладання, яке ми використали.

Але наше $c$ повинно залишатися всередині [l,r], тому з блоку $C$ розміру $H$ ми зберігаємо лише підінтервал

нехай його довжина буде z \ge 0. Тоді ця пара блоків $(A,B)$ вносить

упорядкованих пар $(a,b)$ з a \oplus b \in [l,r]. Якщо ми підсумуємо це по всіх упорядкованих парах блоків $(A,B)$ з розкладу [l,r], ми отримаємо загальну кількість упорядкованих пар $(a,b)$ в [l,r]^2, чиї xor також лежать в [l,r].

Тепер, як перейти від упорядкованих $(a,b)$ до невпорядкованих трійок \{a,b,c\}? Візьміть будь-яку дійсну трійку різних чисел \{x,y,z\} з z = x \oplus y. З цього набору трьох чисел ви можете утворити шість упорядкованих пар:

Всі вони з'являються в нашому упорядкованому підрахунку. Ми вже стверджували, що жодна дегенерація (як x=y) не може пройти умову [l,r], тому кожна дійсна невпорядкована трійка відповідає точно $6$ упорядкованим парам. Отже,

Оскільки ми працюємо за модулем 10^9+7, ми просто множимо на 6^{-1} \bmod (10^9+7), тобто

Алгоритм на запит:

• розкласти [l,r] на діадичні блоки (s_t, L_t);

• для кожної упорядкованої пари (s_i,L_i), (s_j,L_j):

  • H = \max(L_i,L_j), k = \log_2 H;

  • c_{\text{start}} = \bigl((s_i \gg k) \oplus (s_j \gg k)\bigr) \ll k;

  • c_{\text{end}} = c_{\text{start}} + H - 1;

  • L = \max(l, c_{\text{start}}), R = \min(r, c_{\text{end}});

  • якщо L \le R, тоді z = R - L + 1 і додаємо z \cdot \min(L_i,L_j) до упорядкованої відповіді.

• нарешті, помножити на 6^{-1}.

Кількість блоків є \mathcal{O}(\log (r-l+1)) \le 60, тому один запит складає близько 60^2 операцій, а для 10^4 запитів це нормально за $3$ секунди в C++.

Всі трійки автоматично різні, і нам ніколи не потрібно спеціально обробляти $0$, оскільки 0 \notin [l,r]. Це завершує рішення.

//Автор - MathModel

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1000000007, inv6=166666668;

vector<pair<int,int>> decomp(int l,int r){
    vector<pair<int,int>> s;
    int x=l;
    while(x<=r){
        int len=r-x+1;
        int L=1LL<<(63-__builtin_clzll(len));
        int m=x&-x;
        if(m<L)L=m;
        s.push_back({x,L});
        x+=L;
    }
    return s;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin>>t;
    while(t--){
        int l,r; cin>>l>>r;
        auto S=decomp(l,r);
        int ans=0;
        for(auto [x,L]:S){
            for(auto [y,M]:S){
                int h=max(L,M);
                int k=63-__builtin_clzll(h);
                long long base=((x>>k)^(y>>k))<<k;
                long long z=min(base+h-1,r)-max(base,l)+1;
                if(z>0){
                    int add=(min(L,M)%MOD)*(z%MOD)%MOD;
                    ans=(ans+add)%MOD;
                }
            }
        }
        cout<<ans*inv6%MOD<<'\n';
    }
}

Рішення 2 : Динамічне Програмування

Ми рахуємо упорядковані трійки (a,b,c) в [l,r]^3 з a\oplus b\oplus c=0, потім ділимо на $6$ в кінці (всі дійсні трійки різні, оскільки l\ge1, тому будь-яка рівність змусила б третє бути 0\notin[l,r]).

Зробіть бінарне цифрове DP по бітах k=63,62,\dots,0. На біті $k$, нехай L=(l\!\gg\!k)\&1 і R=(r\!\gg\!k)\&1. Стан DP є

де для кожного числа x\in\{a,b,c\}: - t_x\in\{0,1\} означає "все ще прив'язаний до нижньої межі на вищих бітах" (тому на цьому біті ми не можемо поставити біт менший за $L$, якщо t_x=1), - u_x\in\{0,1\} означає "вже строго нижче верхньої межі на деякому вищому біті" (тому на цьому біті ми можемо вільно використовувати $1$, навіть якщо R=0, коли u_x=1).

З цього стану ми вибираємо поточні біти (x_k,y_k,z_k)\in\{0,1\}^3 з підпорядкованими двома обмеженнями: 1) \textbf{обмеження діапазону} для кожного числа: x_k \in \big[\, \underbrace{t_a?L:0}_{\text{мін}},\ \underbrace{u_a?1:R}_{\text{макс}} \,\big],\quad y_k \in \big[\, t_b?L:0,\ u_b?1:R \,\big],\quad z_k \in \big[\, t_c?L:0,\ u_c?1:R \,\big]; 2) \textbf{обмеження xor} на цьому біті: x_k \oplus y_k \oplus z_k = 0, інакше нижчі біти ніколи не можуть виправити невідповідність. Для кожної дійсної трійки бітів ми переходимо до наступного біта з оновленими прапорами щільності: t_a' = t_a \land (x_k = L),\qquad u_a' = u_a \lor (x_k < R), $іаналогічнодля$b,c$.Базовийвипадокє$F(-1,)=1 (всі біти зафіксовані послідовно). Відповідь DP є кількість упорядкованих трійок; нарешті виводимо \text{ans} \equiv F(63,1,1,1,0,0,0)\cdot 6^{-1}\ \ (\bmod\,10^9+7),\qquad 6^{-1}\equiv 166666668. $Кількістьстанівє$642^6$,ікоженстанпробуємаксимум$8 виборів бітів, тому це незначно. Це все DP. Складність O(2^15)$ на тестовий випадок.

//Автор - SashaT9 

#include <cstring>
#include <iostream>

using namespace std;

constexpr int MOD = 1'000'000'007, INV6 = 166'666'668;
int dp[64][2][2][2][2][2][2];
void add(int &a, int b) { a = (a + b) % MOD; }
int calc(long long l, long long r, int bit = 63, int f1 = 1, int f2 = 1,
         int f3 = 1, int f4 = 0, int f5 = 0, int f6 = 0) {
    if (bit < 0)
        return 1;
    if (dp[bit][f1][f2][f3][f4][f5][f6] != -1) {
        return dp[bit][f1][f2][f3][f4][f5][f6];
    }
    int ans = 0;
    int l_b = (l >> bit) & 1;
    int r_b = (r >> bit) & 1;
    for (int a = min(l_b, f1); a <= max(r_b, f4); ++a) {
        for (int b = min(l_b, f2); b <= max(r_b, f5); ++b) {
            for (int c = min(l_b, f3); c <= max(r_b, f6); ++c) {
                if ((a ^ b ^ c) > 0)
                    continue;
                add(ans, calc(l, r, bit - 1, f1 & (a <= l_b), f2 & (b <= l_b),
                              f3 & (c <= l_b), f4 | (a < r_b), f5 | (b < r_b),
                              f6 | (c < r_b)));
            }
        }
    }
    return dp[bit][f1][f2][f3][f4][f5][f6] = ans;
}
int main() {
    int _;
    cin >> _;
    while (_--) {
        memset(dp, -1, sizeof(dp));
        long long l, r;
        cin >> l >> r;
        cout << 1LL * calc(l, r) * INV6 % MOD << endl;
    }
}