Kaosar and Triples (Editorial)

Solution 1 : \mathcal{O}(\log(r-l+1)) blocks

We want to count unordered triples \{a,b,c\} with l \le a,b,c \le r and

But note that the three equations are actually the same condition: if a \oplus b = c then

and similarly b \oplus c = a. So the whole problem is just: count triples (a,b,c) with c = a \oplus b and all of them lie in [l,r]. Also, if a=b then c=0, which is $<l$ (because l \ge 1), so no valid triple has equal elements; the same for a=c or b=c. So every valid triple has three distinct numbers.

A direct \mathcal{O}((r-l+1)^2) over all pairs $(a,b)$ is impossible since $r$ can be up to 10^{18}. The trick for xor on an interval is to cut [l,r] into \mathcal{O}(\log(r-l+1)) blocks (power-of-two blocks) that are aligned.

Concretely, we do the well-known decomposition: starting from x=l, each time take the biggest power-of-two segment starting at $x$ that does not pass $r$ and is aligned to its length, push it to a list, and move $x$ forward. This produces a set

where each L_t is a power of two, and s_t \equiv 0 \pmod{L_t}. The number of such blocks is \mathcal{O}(\log(r-l+1)).

Now take two such blocks

with L=2^i and M=2^j. There is a standard property for these aligned blocks: if H = \max(L,M) and k = \log_2 H, then the set

is exactly one aligned block

Moreover (this is the key counting fact): each number $c$ in that block $C$ has exactly \min(L,M) preimage pairs $(a,b)$ with a \in A, b \in B and a \oplus b = c. Intuitively: the larger block (the one of size $H$) decides the whole shape of the xor image, and the smaller block just tells you how many ways you can land on each particular xor value. This is exactly the property you get from the specific dyadic decomposition we used.

But our $c$ has to stay inside [l,r], so from the block $C$ of size $H$ we only keep the sub-interval

let its length be z \ge 0. Then this pair of blocks $(A,B)$ contributes

ordered pairs $(a,b)$ with a \oplus b \in [l,r]. If we sum this over all ordered block pairs $(A,B)$ from the decomposition of [l,r], we get the total number of ordered pairs $(a,b)$ in [l,r]^2 whose xor also lies in [l,r].

Now, how do we go from ordered $(a,b)$ to unordered triples \{a,b,c\}? Take any valid triple of distinct numbers \{x,y,z\} with z = x \oplus y. From this set of three numbers you can form six ordered pairs:

All of them appear in our ordered counting. We already argued no degeneracy (like x=y) can pass the [l,r] condition, so every valid unordered triple corresponds to exactly $6$ ordered pairs. Therefore

Since we work modulo 10^9+7, we just multiply by 6^{-1} \bmod (10^9+7), i.e.

The algorithm per query is:

• decompose [l,r] into dyadic blocks (s_t, L_t);

• for every ordered pair (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}});

  • if L \le R then z = R - L + 1 and add z \cdot \min(L_i,L_j) to the ordered answer.

• finally multiply by 6^{-1}.

The number of blocks is \mathcal{O}(\log (r-l+1)) \le 60, so one query is about 60^2 operations, and for 10^4 queries it is fine in $3$ seconds in C++.

All triples are distinct automatically, and we never need to special-case $0$ since 0 \notin [l,r]. That finishes the solution.

//Author is 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';
    }
}

Solution 2 : Dynamic Programming

We count ordered triples (a,b,c) in [l,r]^3 with a\oplus b\oplus c=0, then divide by $6$ at the end (all valid triples are distinct since l\ge1, so any equality would force the third to be 0\notin[l,r]).

Do a binary digit-DP over bits k=63,62,\dots,0. At bit $k$, let L=(l\!\gg\!k)\&1 and R=(r\!\gg\!k)\&1. The DP state is

where for each number x\in\{a,b,c\}: - t_x\in\{0,1\} means "still tight to the lower bound at higher bits" (so at this bit we cannot put a bit smaller than $L$ if t_x=1), - u_x\in\{0,1\} means "already strictly below the upper bound at some higher bit" (so at this bit we may freely use $1$ even if R=0 when u_x=1).

From this state we choose the current bits (x_k,y_k,z_k)\in\{0,1\}^3 subject to two constraints: 1) range constraint for each number:

2) xor constraint at this bit:

otherwise lower bits can never fix the mismatch.

For each valid triple of bits we go to the next bit with updated tightness flags:

and analogously for $b,c$. The base case is F(-1,\cdot)=1 (all bits fixed consistently). The answer of the DP is the number of ordered triples; finally output

State count is 64\cdot 2^6 and each state tries at most $8$ bit choices, so it's tiny. That's the whole DP.

Complexity \mathcal{O}(2^{15}) per test case.

//Author is 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;
    }
}