Kaosar and Count ORz#12436

Kaosar and Count ORz (Розбір)

Автор задачі:	Al_Kaosar
Підготував:	MathModel
Відредагував:	MathModel

Розв'язання

Щоб виконувалася умова побітового OR $x ∣ y = n$ x \ | \ y = n, потрібно розглядати кожну бітову позицію $i$ незалежно. Нехай $n_{i}, x_{i},$ n_i, x_i, і $y_{i}$ y_i — це $i$ -ті біти чисел $n, x,$ і $y$ відповідно.

Якщо $n_{i} = 0$ n_i = 0: єдина можливість — це $x_{i} = 0$ x_i = 0 і $y_{i} = 0$ y_i = 0. (1 варіант)
Якщо $n_{i} = 1$ n_i = 1: пара $(x_{i}, y_{i})$ (x_i, y_i) може бути $(0, 1), (1, 0),$ (0, 1), (1, 0), або $(1, 1)$ . (3 варіанти)

Нехай $k$ — кількість встановлених бітів (population count) у числі $n$ . Тоді загальна кількість пар $(x, y)$ таких, що $0 \leq x, y \leq n$ 0 \le x, y \le n і $x ∣ y = n$ x \ | \ y = n, дорівнює рівно $3^{k}$ 3^k. Зауважимо, що обмеження $x, y \leq n$ x, y \le n виконується автоматично, оскільки $x$ і $y$ є підмасками числа $n$ .

У задачі вимагається, щоб $1 \leq x, y \leq n$ 1 \le x, y \le n. Тому потрібно виключити випадки, коли $x = 0$ x=0 або $y = 0$ y=0:

Якщо $x = 0$ x=0, тоді $0 ∣ y = n ⟹ y = n$ 0 \ | \ y = n \implies y = n. Це дає пару $(0, n)$ .
Якщо $y = 0$ y=0, тоді $x ∣ 0 = n ⟹ x = n$ x \ | \ 0 = n \implies x = n. Це дає пару $(n, 0)$ .

Оскільки в усіх наборах входних даних $n \geq 1$ n \ge 1, ці дві пари різні. Отже, від загальної кількості потрібно відняти 2. Остаточна відповідь дорівнює $(3^{k} - 2) (mod 1 0^{9} + 7)$ (3^k - 2) \pmod{10^9+7}.

Складність для одного набору входних даних становить $O (lo g n)$ O(\log n) завдяки модульному піднесенню до степеня.

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