Kaosar və OR cütlərinin sayı#12436

Kaosar və OR cütlərinin sayı (Həll təhlili)

Problem Author:	Al_Kaosar
Prepared by:	MathModel
Edited by:	MathModel

Həll

$x ∣ y = n$ x \ | \ y = n bitlər üzrə OR şərtinin ödənməsi üçün hər bit mövqeyini $i$ ayrıca nəzərdən keçirməliyik. $n_{i}, x_{i},$ n_i, x_i, və $y_{i}$ y_i uyğun olaraq $n, x,$ və $y$ -nin $i$ -ci bitləri olsun.

Əgər $n_{i} = 0$ n_i = 0 olarsa: Yeganə mümkün hal $x_{i} = 0$ x_i = 0 və $y_{i} = 0$ y_i = 0-dır. (1 seçim)
Əgər $n_{i} = 1$ n_i = 1 olarsa: $(x_{i}, y_{i})$ (x_i, y_i) cütü $(0, 1), (1, 0),$ (0, 1), (1, 0), və ya $(1, 1)$ ola bilər. (3 seçim)

Qoy $k$ $n$ ədədindəki qurulmuş bitlərin (population count) sayı olsun. Onda $0 \leq x, y \leq n$ 0 \le x, y \le n və $x ∣ y = n$ x \ | \ y = n şərtini ödəyən $(x, y)$ cütlərinin ümumi sayı dəqiq olaraq $3^{k}$ 3^k-dir. Diqqət edin ki, $x, y \leq n$ x, y \le n məhdudiyyəti təbii şəkildə ödənir, çünki $x$ və $y$ , $n$ -in altmaskalarıdır.

Məsələdə isə $1 \leq x, y \leq n$ 1 \le x, y \le n tələb olunur. Buna görə də $x = 0$ x=0 və ya $y = 0$ y=0 olan halları çıxmalıyıq:

Əgər $x = 0$ x=0 olarsa, onda $0 ∣ y = n ⟹ y = n$ 0 \ | \ y = n \implies y = n. Bu, $(0, n)$ cütünü verir.
Əgər $y = 0$ y=0 olarsa, onda $x ∣ 0 = n ⟹ x = n$ x \ | \ 0 = n \implies x = n. Bu, $(n, 0)$ cütünü verir.

Bütün набор входных данных-larda $n \geq 1$ n \ge 1 olduğuna görə bu iki cüt fərqlidir. Deməli, ümumi saydan 2 çıxırıq. Son cavab $(3^{k} - 2) (mod 1 0^{9} + 7)$ (3^k - 2) \pmod{10^9+7} olur.

Hər bir набор входных данных üçün mürəkkəblik modullu qüvvətə yüksəltməyə görə $O (lo g n)$ O(\log n)-dir.

for _ in range(int(input())):
    n=int(input())
    k=n.bit_count()
    mod=10**9+7
    print((pow(3,k,mod)-2)%mod)