Kaosar və Üçlüklər (Həll təhlili)

Həll 1 : \mathcal{O}(\log(r-l+1)) blokları

Biz l \le a,b,c \le r olan sırasız üçlükləri \{a,b,c\} saymaq istəyirik və

Amma qeyd edin ki, bu üç tənlik əslində eyni şərti ifadə edir: əgər a \oplus b = c isə, onda

və eyni şəkildə b \oplus c = a. Beləliklə, bütün problem sadəcə: c = a \oplus b olan üçlükləri (a,b,c) saymaqdır və onların hamısı [l,r] aralığında yerləşir. Həmçinin, əgər a=b olarsa, onda c=0 olur, bu da $<l$-dir (çünki l \ge 1), buna görə də heç bir etibarlı üçlük bərabər elementlərə malik deyil; a=c və ya b=c üçün də eynidir. Beləliklə, hər etibarlı üçlük üç fərqli ədədə malikdir.

Birbaşa \mathcal{O}((r-l+1)^2) bütün $(a,b)$ cütləri üçün mümkün deyil, çünki $r$ 10^{18}-ə qədər ola bilər. Aralıqda xor üçün fənd [l,r]-ni \mathcal{O}(\log(r-l+1)) bloklara (iki güc blokları) bölməkdir.

Konkret olaraq, biz yaxşı tanınan dekompozisiyanı edirik: x=l-dən başlayaraq, hər dəfə $x$-dən başlayan ən böyük iki güc seqmentini götürürük ki, bu seqment $r$-dən keçməsin və uzunluğuna uyğun olsun, onu bir siyahıya əlavə edirik və $x$-i irəliləyirik. Bu, aşağıdakı dəsti yaradır

burada hər L_t iki gücdür və s_t \equiv 0 \pmod{L_t}. Belə blokların sayı \mathcal{O}(\log(r-l+1))-dir.

İndi iki belə bloku götürün

burada L=2^i və M=2^j. Bu uyğun bloklar üçün standart bir xüsusiyyət var: əgər H = \max(L,M) və k = \log_2 H, onda

tam olaraq bir uyğun blokdur

Bundan əlavə (bu, sayma faktıdır): bu blokdakı hər ədəd $c$ tam olaraq \min(L,M) əvvəlki şəkil cütlərinə $(a,b)$ malikdir ki, a \in A, b \in B və a \oplus b = c. İntuitiv olaraq: daha böyük blok (ölçüsü $H$ olan) xor görüntüsünün bütün formasını müəyyən edir, və daha kiçik blok sadəcə sizə hər bir xüsusi xor dəyərinə necə düşə biləcəyinizi bildirir. Bu, istifadə etdiyimiz spesifik dyadik dekompozisiyadan əldə etdiyiniz xüsusiyyətdir.

Amma bizim $c$ [l,r] daxilində qalmalıdır, buna görə də $C$ blokundan ölçüsü $H$ olan yalnız aşağıdakı alt-aralığı saxlayırıq

bunun uzunluğunu z \ge 0 qoyun. Sonra bu blok cütü $(A,B)$ aşağıdakı sayda

sıralı cüt $(a,b)$ ilə a \oplus b \in [l,r]-də iştirak edir. Əgər biz bunu [l,r]-nin dekompozisiyasından bütün sıralı blok cütləri $(A,B)$ üzərində toplasaq, [l,r]^2-dəki $(a,b)$ cütlərinin cəmini alırıq ki, xor da [l,r]-dədir.

İndi, sıralı $(a,b)$-dən sırasız üçlüklərə \{a,b,c\} necə keçirik? Hər hansı etibarlı fərqli ədəd üçlüyü \{x,y,z\} götürün ki, z = x \oplus y. Bu üç ədəd dəstindən altı sıralı cüt yarada bilərsiniz:

Onların hamısı bizim sıralı sayımımızda görünür. Artıq heç bir degenerasiya (məsələn, x=y) [l,r] şərtini keçə bilməz, buna görə də hər etibarlı sırasız üçlük tam olaraq $6$ sıralı cütə uyğun gəlir. Buna görə də

Biz 10^9+7 modulu ilə işlədiyimiz üçün, sadəcə 6^{-1} \bmod (10^9+7) ilə vururuq, yəni

Sorğu başına alqoritm:

• [l,r]-ni dyadik bloklara (s_t, L_t)-ya ayırın;

• hər sıralı cüt (s_i,L_i), (s_j,L_j) üçün:

  • 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}});

  • əgər L \le R-dirsə, onda z = R - L + 1 və sıralı cavaba z \cdot \min(L_i,L_j) əlavə edin.

• nəhayət, 6^{-1} ilə vurun.

Blokların sayı \mathcal{O}(\log (r-l+1)) \le 60-dır, buna görə də bir sorğu təxminən 60^2 əməliyyatdır, və 10^4 sorğu üçün bu C++-da 3 saniyədə normaldır.

Bütün üçlüklər avtomatik olaraq fərqlidir və biz heç vaxt $0$-ı xüsusi hal kimi nəzərə almırıq, çünki 0 \notin [l,r]. Bu, həlli tamamlayır.

//Müəllif 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';
    }
}

Həll 2 : Dinamik Proqramlaşdırma

Biz [l,r]^3 aralığında a\oplus b\oplus c=0 olan sıralı üçlükləri (a,b,c) sayırıq, sonra sonunda $6$-ya bölürük (bütün etibarlı üçlüklər fərqlidir, çünki l\ge1, buna görə də hər hansı bərabərlik üçüncü ədədin 0\notin[l,r] olmasına səbəb olardı).

Bitlər k=63,62,\dots,0 üzərində ikili bit-DP aparın. Bit $k$-də L=(l\!\gg\!k)\&1 və R=(r\!\gg\!k)\&1. DP vəziyyəti

hər bir ədəd x\in\{a,b,c\} üçün: - t_x\in\{0,1\} "yuxarı bitlərdə aşağı sərhədə hələ də sıx bağlıdır" deməkdir (beləliklə, bu bitdə t_x=1 olduqda $L$-dan kiçik bir bit qoymaq mümkün deyil), - u_x\in\{0,1\} "hansısa yuxarı bitdə artıq sərt şəkildə yuxarı sərhəddən aşağıdır" deməkdir (beləliklə, bu bitdə R=0 olduqda u_x=1 olduqda $1$ istifadə edə bilərsiniz).

Bu vəziyyətdən biz cari bitləri (x_k,y_k,z_k)\in\{0,1\}^3 seçirik, iki məhdudiyyətə tabe olaraq: 1) Hər ədəd üçün \textbf{aralıq məhdudiyyəti}: x_k \in \big[\, \underbrace{t_a?L:0}_{\text{minimum}},\ \underbrace{u_a?1:R}_{\text{maksimum}} \,\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) Bu bitdə \textbf{xor məhdudiyyəti}: x_k \oplus y_k \oplus z_k = 0, əks halda aşağı bitlər heç vaxt uyğunsuzluğu düzəldə bilməz. Hər etibarlı bit üçlüyü üçün biz növbəti bitə keçirik, sıxlıq bayraqlarını yeniləyərək: t_a' = t_a \land (x_k = L),\qquad u_a' = u_a \lor (x_k < R), $və$b,c üçün analoji. Baz vəziyyəti F(-1,)=1-dir (bütün bitlər ardıcıl olaraq düzəldilmişdir). DP-nin cavabı sıralı üçlüklərin sayıdır; nəhayət, çıxış \text{cavab} \equiv F(63,1,1,1,0,0,0)\cdot 6^{-1}\ \ (\bmod\,10^9+7),\qquad 6^{-1}\equiv 166666668. Vəziyyət sayı 642^6-dır və hər vəziyyət ən çox 8 bit seçimi sınayır, buna görə də bu kiçikdir. Bu, bütün DP-dir. Komplekslik O(2^15)$ hər test halı üçün.

//Müəllif 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;
    }
}