Kaosar y XOR#12228

Kaosar y XOR (Editorial)

Autor del Problema:	Al Kaosar Hussain
Preparado por:	Hasan Saleh (MathModel)
Editado por:	Hasan Saleh (MathModel)

Solución Puedes escribir un enfoque de fuerza bruta en $O (n^{2})$ \mathcal{O}(n^2) y observar lo siguiente:

Para algún entero $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}

Prueba :

Punto 1 :

Para algunos enteros $n \leq 2^{m}$ n \le 2^m, entonces todos $1 \leq i, j \leq n$ 1 \le i,j \le n tienen $popcnt (i \oplus j) < 2^{m}$ \text{popcnt}(i \oplus j) < 2^m.

Punto 2 :

Escribe $x$ en binario con un máximo de $m$ bits. Deja que su bit más alto establecido esté en la posición $k < m$ k<m. Luego elige $i = 2^{k}$ i=2^k, $j = i \oplus x$ j=i \oplus x, dado que $x < 2^{m}$ x<2^m, tenemos $j < 2^{m}$ j<2^m y porque $n > 2^{m - 1}$ n>2^{m-1}, entonces $i \oplus j = x$ i \oplus j=x.

Punto 3 : Para potencias de 2, el mismo proceso ocurre con la exclusión del bit más alto $(2^{m - 1})$ (2^{m-1}), y por lo tanto la respuesta es $2 n - 2$ 2n-2 en ese caso.


#if n=potencia de 2 entonces respuesta 2*n-2
#if n no es potencia de 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

Complejidad $O (lo g (n))$ .