Kapitan Cek Sparrow#12293

Kapitan Cek Sparrow (Həll təhlili)

Problem Müəllifi:	Akbar Akbar
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Hər test halı üçün aşağıdakı dəyəri hesablamağımız lazımdır:

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 olan terminlər $(r - l)$ (r-l) faktoru səbəbindən sıfır töhfə verir, buna görə də $a \leq l < r \leq b$ a\le l<r\le b olan bütün cütlər üzrə cəmi yenidən yaza bilərik. Əsas addım XOR-u standart identiklikdən istifadə edərək çıxarmaqdır:

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

beləliklə

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

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

Beləliklə, cavab aşağıdakı kimi olur:

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

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

burada

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

Notasiyaları daha aydın etmək üçün, yenidən indeksləyirik. $n = b - a + 1$ n = b-a+1 götürək və $x_{i} = a + i$ x_i = a+i üçün $i = 0, \dots, n - 1$ i=0,\dots,n-1 müəyyən edək. $a \leq l < r \leq b$ a\le l<r\le b olan hər cüt $(l, r)$ (l,r) $0 \leq i < j < n$ 0\le i<j<n olan $(x_{i}, x_{j})$ (x_i,x_j) ilə uyğun gəlir və

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

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

Sonra

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 üçün, bütün cütlər üzrə cəmləmək əvəzinə, hər bir indeks $k$ -nın töhfəsinə ayrıca baxırıq. $x_{k}$ x_k elementi sağ ucu $(i, k)$ cütlərində $i = 0, \dots, k - 1$ i=0,\dots,k-1 ilə görünür və bu cütlərin toplam məsafəsi

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

Eyni zamanda, o, sol ucu $(k, j)$ (k,j) cütlərində $j = k + 1, \dots, n - 1$ j=k+1,\dots,n-1 ilə görünür, bu da

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

Beləliklə, indeks $k$ üçün toplam məsafə çəkisi

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

və

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.

Bu, $k$ üzrə bir döngü ilə, hər şeyi $1 0^{9} + 7$ 10^9+7 modulunda edərək həyata keçirilir.

$S_{2}$ S_2 üçün, bitləri idarə edirik. Yazmaq olar

x_{i} & x_{j} = b = 0 \sum 30 ((1 ≪ b) əgər bit b hər iki x_{i}, x_{j} u ¨ c ¸ u ¨ n təyin olunubsa),

x_i\&x_j = \sum_{b=0}^{30} \left( (1\ll b)\ \text{əgər bit }b\text{ hər iki }x_i,x_j\text{ üçün təyin olunubsa} \right),

beləliklə

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

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

burada

T_{b} = 0 \leq i < j < n bit b hər iki x_{i}, x_{j} u ¨ c ¸ u ¨ n təyin olunub \sum (j - i) .

T_b = \sum_{\substack{0\le i<j<n \\ \text{bit }b\text{ hər iki }x_i,x_j\text{ üçün təyin olunub}}} (j-i).

Bəzi bit $b$ -ni düzəldin. Yalnız bu bitin təyin olunduğu indekslərə baxın. Bu indekslərin artan sırası $p_{0}, p_{1}, \dots, p_{m - 1}$ p_0,p_1,\dots,p_{m-1} olsun. Onda

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

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

Bunu bir keçid ilə hesablaya bilərik, cütləri açıq şəkildə saxlamadan. $p_{v}$ p_v-ni işlədərkən, onun bütün əvvəlki indekslərlə töhfəsi

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.

Beləliklə, hər bit $b$ üçün saxlayırıq:

$cnt_{b}$ \text{cnt}_b = o bitin təyin olunduğu indekslərin sayı (bu $v$ -dir),
$sumIdx_{b}$ \text{sumIdx}_b = bu indekslərin cəmi,
$T_{b}$ T_b = bu bit üçün toplanmış dəyər.

İndeks $i$ -də olarkən, $x = a + i$ x = a + i olsun. $x$ -nin $j$ -ci bitinin $1$ olduğu hər bit üçün, biz yeniləyirik

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.

Sonda, hər bit üçün $T_{b}$ T_b məlumdur və

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

burada $MOD = 1 0^{9} + 7$ \text{MOD}=10^9+7. Son cavab

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

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

Komplekslik $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