Captain Jack Sparrow#12293

Captain Jack Sparrow (Editorial)

Problem Author:	Akbar Akbar
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

We need to compute, for each test case, the value

l = a \sum b r = l \sum b ((l \oplus r) + (l & r)) \cdot (r - l) (mod 1 0^{9} + 7) .

\sum_{l=a}^{b}\sum_{r=l}^{b}\big((l\oplus r)+(l\&r)\big)\cdot(r-l)\pmod{10^9+7}.

The terms with $r = l$ r=l contribute zero because of the factor $(r - l)$ (r-l), so we can rewrite the sum over all pairs with $a \leq l < r \leq b$ a\le l<r\le b. The key step is to remove the XOR using the standard identity

l + r = (l \oplus r) + 2 (l & r) \Rightarrow (l \oplus r) = l + r - 2 (l & r),

l + r = (l \oplus r) + 2(l \& r) \quad\Rightarrow\quad (l\oplus r) = l + r - 2(l\&r),

therefore

(l \oplus r) + (l & r) = l + r - (l & r) .

(l\oplus r)+(l\&r) = l + r - (l\&r).

So the answer becomes

Ans = a \leq l < r \leq b \sum (l + r - (l & r)) (r - l) = S_{1} - S_{2},

\mathsf{Ans} = \sum_{a\le l<r\le b} (l + r - (l\&r))(r-l) = S_1 - S_2,

where

S_{1} = a \leq l < r \leq b \sum (l + r) (r - l), S_{2} = a \leq l < r \leq b \sum (l & r) (r - l) .

S_1 = \sum_{a\le l<r\le b}(l+r)(r-l), \qquad S_2 = \sum_{a\le l<r\le b}(l\&r)(r-l).

To make the notation cleaner, we reindex. Let $n = b - a + 1$ n = b-a+1 and define $x_{i} = a + i$ x_i = a+i for $i = 0, \dots, n - 1$ i=0,\dots,n-1. Any pair $(l, r)$ (l,r) with $a \leq l < r \leq b$ a\le l<r\le b corresponds to $(x_{i}, x_{j})$ (x_i,x_j) with $0 \leq i < j < n$ 0\le i<j<n, and

r - l = x_{j} - x_{i} = (a + j) - (a + i) = j - i .

r - l = x_j - x_i = (a+j)-(a+i) = j-i.

Then

S_{1} = 0 \leq i < j < n \sum (x_{i} + x_{j}) (j - i), S_{2} = 0 \leq i < j < n \sum (x_{i} & x_{j}) (j - i) .

S_1 = \sum_{0\le i<j<n}(x_i+x_j)(j-i), \qquad S_2 = \sum_{0\le i<j<n}(x_i\&x_j)(j-i).

For $S_{1}$ S_1, instead of summing over all pairs, we look at the contribution of each index $k$ separately. The element $x_{k}$ x_k appears in pairs as a right endpoint $(i, k)$ with $i = 0, \dots, k - 1$ i=0,\dots,k-1, and the total distance from those is

i = 0 \sum k - 1 (k - i) = 1 + 2 + \dots + k = \frac{k ( k + 1 )}{2} .

\sum_{i=0}^{k-1}(k-i) = 1+2+\dots+k = \frac{k(k+1)}{2}.

It also appears as a left endpoint $(k, j)$ (k,j) with $j = k + 1, \dots, n - 1$ j=k+1,\dots,n-1, giving

j = k + 1 \sum n - 1 (j - k) = 1 + 2 + \dots + (n - k - 1) = \frac{( n - k - 1 ) ( n - k )}{2} .

\sum_{j=k+1}^{n-1}(j-k) = 1+2+\dots+(n-k-1) = \frac{(n-k-1)(n-k)}{2}.

So the total distance weight for index $k$ is

W_{k} = \frac{k ( k + 1 )}{2} + \frac{( n - k - 1 ) ( n - k )}{2},

W_k = \frac{k(k+1)}{2} + \frac{(n-k-1)(n-k)}{2},

and

S_{1} = k = 0 \sum n - 1 x_{k} W_{k} = k = 0 \sum n - 1 (a + k) W_{k} .

S_1 = \sum_{k=0}^{n-1} x_k W_k = \sum_{k=0}^{n-1}(a+k)W_k.

This is just one loop over $k$ , doing everything modulo $1 0^{9} + 7$ 10^9+7.

For $S_{2}$ S_2, we handle bits. We can write

x_{i} & x_{j} = b = 0 \sum 30 ((1 ≪ b) if bit b is set in both x_{i}, x_{j}),

x_i\&x_j = \sum_{b=0}^{30} \left( (1\ll b)\ \text{if bit }b\text{ is set in both }x_i,x_j \right),

S_{2} = b = 0 \sum 30 (1 ≪ b) \cdot T_{b},

S_2 = \sum_{b=0}^{30} (1\ll b)\cdot T_b,

where

T_{b} = 0 \leq i < j < n bit b set in both x_{i}, x_{j} \sum (j - i) .

T_b = \sum_{\substack{0\le i<j<n \\ \text{bit }b\text{ set in both }x_i,x_j}} (j-i).

Fix some bit $b$ . Consider only indices where this bit is set. Suppose their indices in increasing order are $p_{0}, p_{1}, \dots, p_{m - 1}$ p_0,p_1,\dots,p_{m-1}. Then

T_{b} = 0 \leq u < v < m \sum (p_{v} - p_{u}) .

T_b = \sum_{0\le u<v<m}(p_v-p_u).

We can compute this in one pass without explicitly storing pairs. When we process $p_{v}$ p_v, its contribution with all previous indices is

u = 0 \sum v - 1 (p_{v} - p_{u}) = v \cdot p_{v} - u = 0 \sum v - 1 p_{u} .

\sum_{u=0}^{v-1}(p_v-p_u) = v\cdot p_v - \sum_{u=0}^{v-1}p_u.

So we maintain for each bit $b$ :

$cnt_{b}$ \text{cnt}_b = count of indices seen with that bit set (this is $v$ ),
$sumIdx_{b}$ \text{sumIdx}_b = sum of those indices,
$T_{b}$ T_b = accumulated value for this bit.

When we are at index $i$ , let $x = a + i$ x = a + i. For each bit $j$ such that the $j$ -th bit of $x$ is $1$ , we update

T_{j} + = cnt_{j} \cdot i - sumIdx_{j}, cnt_{j} + = 1, sumIdx_{j} + = i .

T_j \mathrel{+}= \text{cnt}_j\cdot i - \text{sumIdx}_j, \qquad \text{cnt}_j \mathrel{+}= 1, \qquad \text{sumIdx}_j \mathrel{+}= i.

At the end, $T_{b}$ T_b is known for each bit, and

S_{2} = b = 0 \sum 30 (T_{b} mod MOD) \cdot ((1 ≪ b) mod MOD) mod MOD,

S_2 = \sum_{b=0}^{30} (T_b \bmod \text{MOD})\cdot((1\ll b)\bmod \text{MOD})\bmod \text{MOD},

with $MOD = 1 0^{9} + 7$ \text{MOD}=10^9+7. The final answer is

Ans = (S_{1} - S_{2}) mod MOD .

\mathsf{Ans} = (S_1 - S_2)\bmod \text{MOD}.

Complexity $O (n + n \cdot lo g n)$ \mathcal{O}(n + n\cdot\log n)

MOD=10**9+7
for _ in range(int(input())):
    a,b=map(int, input().split())
    n=b-a+1
    s1=0
    for i in range(n):
        l=i*(i+1)//2
        r=(n-i-1)*(n-i)//2
        w=l+r
        s1=(s1+(a+i)%MOD*(w%MOD))%MOD

    c=[0]*31
    si=[0]*31
    t=[0]*31
    for i in range(n):
        x=a+i
        for j in range(31):
            if(x>>j&1):
                t[j]+=c[j]*i-si[j]
                c[j]+=1
                si[j]+=i

    s2=0
    for j in range(31):
        s2=(s2+(t[j]%MOD)*((1<<j)%MOD))%MOD
    print((s1-s2)%MOD)

Python