Kaosar and Count ORz#12436

Kaosar and Count ORz (Editorial)

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

Solution

For the bitwise OR condition $x ∣ y = n$ x \ | \ y = n to hold, we must consider each bit position $i$ independently. Let $n_{i}, x_{i},$ n_i, x_i, and $y_{i}$ y_i be the $i$ -th bits of $n, x,$ and $y$ respectively.

If $n_{i} = 0$ n_i = 0: The only possibility is $x_{i} = 0$ x_i = 0 and $y_{i} = 0$ y_i = 0. (1 choice)
If $n_{i} = 1$ n_i = 1: The pair $(x_{i}, y_{i})$ (x_i, y_i) can be $(0, 1), (1, 0),$ (0, 1), (1, 0), or $(1, 1)$ . (3 choices)

Let $k$ be the number of set bits (population count) in $n$ . The total number of pairs $(x, y)$ such that $0 \leq x, y \leq n$ 0 \le x, y \le n and $x ∣ y = n$ x \ | \ y = n is exactly $3^{k}$ 3^k. Note that the constraint $x, y \leq n$ x, y \le n is naturally satisfied because $x$ and $y$ are submasks of $n$ .

The problem requires $1 \leq x, y \leq n$ 1 \le x, y \le n. Therefore, we must exclude cases where $x = 0$ x=0 or $y = 0$ y=0:

If $x = 0$ x=0, then $0 ∣ y = n ⟹ y = n$ 0 \ | \ y = n \implies y = n. This gives the pair $(0, n)$ .
If $y = 0$ y=0, then $x ∣ 0 = n ⟹ x = n$ x \ | \ 0 = n \implies x = n. This gives the pair $(n, 0)$ .

Since $n \geq 1$ n \ge 1 in all test cases, these two pairs are distinct. Thus, we subtract 2 from our total count. The final answer is $(3^{k} - 2) (mod 1 0^{9} + 7)$ (3^k - 2) \pmod{10^9+7}.

The complexity per test case is $O (lo g n)$ O(\log n) due to modular exponentiation.

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