Капітан Джек Горобець#12293

Капітан Джек Горобець (Розбір)

Автор проблеми:	Акбар Акбар
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Розв'язок

Нам потрібно обчислити, для кожного тестового випадку, значення

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}.

Члени з $r = l$ r=l не вносять внесок, оскільки є множник $(r - l)$ (r-l), тому ми можемо переписати суму для всіх пар з $a \leq l < r \leq b$ a\le l<r\le b. Ключовим кроком є видалення XOR, використовуючи стандартну ідентичність

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),

тому

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

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

Отже, відповідь стає

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,

де

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).

Щоб зробити нотацію чистішою, ми переіндексуємо. Нехай $n = b - a + 1$ n = b-a+1 і визначимо $x_{i} = a + i$ x_i = a+i для $i = 0, \dots, n - 1$ i=0,\dots,n-1. Будь-яка пара $(l, r)$ (l,r) з $a \leq l < r \leq b$ a\le l<r\le b відповідає $(x_{i}, x_{j})$ (x_i,x_j) з $0 \leq i < j < n$ 0\le i<j<n, і

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

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

Тоді

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).

Для $S_{1}$ S_1, замість того, щоб підсумовувати всі пари, ми розглядаємо внесок кожного індексу $k$ окремо. Елемент $x_{k}$ x_k з'являється в парах як правий кінець $(i, k)$ з $i = 0, \dots, k - 1$ i=0,\dots,k-1, і загальна відстань від них становить

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}.

Він також з'являється як лівий кінець $(k, j)$ (k,j) з $j = k + 1, \dots, n - 1$ j=k+1,\dots,n-1, що дає

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}.

Отже, загальна вага відстані для індексу $k$ становить

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},

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.

Це просто один цикл по $k$ , виконуючи все за модулем $1 0^{9} + 7$ 10^9+7.

Для $S_{2}$ S_2 ми обробляємо біти. Ми можемо записати

x_{i} & x_{j} = b = 0 \sum 30 ((1 ≪ b) якщо біт b встановлений в обох x_{i}, x_{j}),

x_i\&x_j = \sum_{b=0}^{30} \left( (1\ll b)\ \text{якщо біт }b\text{ встановлений в обох }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,

де

T_{b} = 0 \leq i < j < n біт b встановлений в обох x_{i}, x_{j} \sum (j - i) .

T_b = \sum_{\substack{0\le i<j<n \\ \text{біт }b\text{ встановлений в обох }x_i,x_j}} (j-i).

Фіксуємо деякий біт $b$ . Розглянемо лише індекси, де цей біт встановлений. Нехай їх індекси в зростаючому порядку $p_{0}, p_{1}, \dots, p_{m - 1}$ p_0,p_1,\dots,p_{m-1}. Тоді

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

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

Ми можемо обчислити це за один прохід, не зберігаючи пари. Коли ми обробляємо $p_{v}$ p_v, його внесок з усіма попередніми індексами становить

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.

Отже, ми підтримуємо для кожного біта $b$ :

$cnt_{b}$ \text{cnt}_b = кількість індексів, які були побачені з цим бітом, встановленим (це $v$ ),
$sumIdx_{b}$ \text{sumIdx}_b = сума цих індексів,
$T_{b}$ T_b = накопичене значення для цього біта.

Коли ми знаходимося на індексі $i$ , нехай $x = a + i$ x = a + i. Для кожного біта $j$ , для якого $j$ -й біт $x$ дорівнює $1$ , ми оновлюємо

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.

В кінці, $T_{b}$ T_b відомий для кожного біта, і

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},

з $MOD = 1 0^{9} + 7$ \text{MOD}=10^9+7. Остаточна відповідь

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

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

Складність $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