Kaosar və XOR#12228

Kaosar və XOR (Həll təhlili)

Problemin Müəllifi:	Al Kaosar Hüseyn
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll Siz $O (n^{2})$ \mathcal{O}(n^2) üzrə bir brute force yaza bilərsiniz və aşağıdakıları müşahidə edə bilərsiniz:

Bəzi tam ədəd $k$ üçün

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

Sübut :

1-ci nöqtə :

Bəzi tam ədədlər $n \leq 2^{m}$ n \le 2^m olduqda, onda bütün $1 \leq i, j \leq n$ 1 \le i,j \le n üçün bütün $popcnt (i \oplus j) < 2^{m}$ \text{popcnt}(i \oplus j) < 2^m.

2-ci nöqtə :

$x$ -i ən çox $m$ bitdə ikili formada yazın. Onun ən yüksək bitinin yeri $k < m$ k<m olsun. Onda $i = 2^{k}$ i=2^k, $j = i \oplus x$ j=i \oplus x seçin, çünki $x < 2^{m}$ x<2^m, $j < 2^{m}$ j<2^m-dir və çünki $n > 2^{m - 1}$ n>2^{m-1}, beləliklə $i \oplus j = x$ i \oplus j=x.

3-cü nöqtə : 2-nin qüvvətləri üçün, eyni proses ən yüksək bitin ( $2^{m - 1}$ 2^{m-1}) istisnası ilə baş verir, buna görə də cavab bu halda $2 n - 2$ 2n-2-dir.


#if n=2-nin qüvvəti, onda cavab 2*n-2
#if n 2-nin qüvvəti deyilsə, 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

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