Каосар та XOR#12228

Каосар та XOR (Розбір)

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

Рішення Ви можете написати брутальне рішення на $O (n^{2})$ \mathcal{O}(n^2) і спостерігати за наступним:

Для деякого цілого числа $k$

{n = 2^{k} ⟹ 2^{k + 1} - 2 n \neq = 2^{k} ⟹ 2^{⌈ l o g_{2} (n)⌉} - 1

\displaystyle \begin{cases} n=2^k \implies 2^{k+1}-2 \\ n \neq 2^k \implies 2^{\lceil \log_2(n) \rceil}-1 \end{cases}

Доказ:

Пункт 1:

Для деяких цілих чисел $n \leq 2^{m}$ n \le 2^m, тоді всі $1 \leq i, j \leq n$ 1 \le i,j \le n, тоді всі $popcnt (i \oplus j) < 2^{m}$ \text{popcnt}(i \oplus j) < 2^m.

Пункт 2:

Запишіть $x$ у двійковій формі з максимум $m$ бітами. Нехай його найвища встановлена бітова позиція буде на позиції $k < m$ k<m. Тоді виберіть $i = 2^{k}$ i=2^k, $j = i \oplus x$ j=i \oplus x, оскільки $x < 2^{m}$ x<2^m, ми маємо $j < 2^{m}$ j<2^m, і оскільки $n > 2^{m - 1}$ n>2^{m-1}, отже, $i \oplus j = x$ i \oplus j=x.

Пункт 3: Для степенів двійки той же процес відбувається з виключенням найвищого біта $(2^{m - 1})$ (2^{m-1}), і тому відповідь у цьому випадку - $2 n - 2$ 2n-2.


#if n=power of 2 then answer 2*n-2
#if n isn't power of 2 , 2^(ceil(log2(n))-1

MOD=10**9+7

p=[1]
cur=1
for i in range(1,62):
    cur*=2
    p.append(cur)
    
def solve():
    n=int(input())
    if(n==2):
        print(1)
        return
    if(n in p):
        print((2*n-2)%MOD)
    else:
        log=0
        while(n>0):
            n//=2
            log+=1
        print((pow(2,log,MOD)-1)%MOD)
for _ in range(int(input())):
    solve()

Python

Складність $O (lo g (n))$ .