Infinite Set (Codeforces 1635D)
Tags: Math, matrices

You are given an array $$$a$$$ consisting of $$$n$$$ distinct positive integers.Let's consider an infinite integer set $$$S$$$ which contains all integers $$$x$$$ that satisfy at least one of the following conditions: $$$x = a_i$$$ for some $$$1 \leq i \leq n$$$. $$$x = 2y + 1$$$ and $$$y$$$ is in $$$S$$$. $$$x = 4y$$$ and $$$y$$$ is in $$$S$$$.For example, if $$$a = [1,2]$$$ then the $$$10$$$ smallest elements in $$$S$$$ will be $$$\{1,2,3,4,5,7,8,9,11,12\}$$$.Find the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Since this number may be too large, print it modulo $$$10^9 + 7$$$.

Input: The first line contains two integers $$$n$$$ and $$$p$$$ $$$(1 \leq n, p \leq 2 \cdot 10^5)$$$.The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.It is guaranteed that all the numbers in $$$a$$$ are distinct.

Output: Print a single integer, the number of elements in $$$S$$$ that are strictly smaller than $$$2^p$$$. Remember to print it modulo $$$10^9 + 7$$$. 

Note: In the first example, the elements smaller than $$$2^4$$$ are $$$\{1, 3, 4, 6, 7, 9, 12, 13, 15\}$$$.In the second example, the elements smaller than $$$2^7$$$ are $$$\{5,11,20,23,39,41,44,47,79,80,83,89,92,95\}$$$.

Sample Inputs:
2 4
6 1

4 7
20 39 5 200

2 200000
48763 1000000000

Sample Outputs:
9

14

448201910

Solution (Python):
import sys
from collections import Counter

def input():
    return sys.stdin.readline()[:-1]

def readline():
    return map(int, input().split())
MOD = 10 ** 9 + 7

def main():
    (n, p) = readline()
    a = sorted(readline())
    values = set()
    for ai in a:
        v = ai
        while v not in values:
            r = v % 4
            if r == 2 or v == 0:
                values.add(ai)
                break
            elif r == 0:
                v //= 4
            else:
                v //= 2
    c = Counter(map(int.bit_length, values))
    x = y = 0
    ans = 0
    for i in range(1, p + 1):
        z = (c.get(i, 0) + x + y) % MOD
        ans += z
        (x, y) = (y, z)
    print(ans % MOD)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def solve(n, p, arr):
    m = 10 ** 9 + 7
    nums = set()
    candidate = []
    arr.sort()
    for num in arr:
        val = num
        while val > 1 and val not in nums:
            if val % 4 == 0:
                val //= 4
            elif val % 2 == 1:
                val //= 2
            else:
                break
        if val not in nums:
            candidate.append(num)
            nums.add(num)
    dp = [0] * p
    numCombs = [0] * p
    dp[-1] = 1
    numCombs[-1] = 1
    if p >= 2:
        dp[-2] = 2
        numCombs[-2] = 3
    idx = p - 3
    while idx > 0:
        dp[idx] = (dp[idx + 1] + dp[idx + 2]) % m
        numCombs[idx] = (dp[idx] + numCombs[idx + 1]) % m
        idx -= 1
    ans = 0
    for num in candidate:
        length = len(bin(num)[2:])
        if length > p:
            continue
        elif length == p:
            ans += 1
            ans %= m
        else:
            ans += numCombs[length] + 1
            ans %= m
    print(ans)
(n, p) = map(int, input().split())
arr = list(map(int, input().split()))
solve(n, p, arr)

Solution (Python):
import sys
from bisect import bisect

def input():
    return sys.stdin.readline()[:-1]

def readline():
    return map(int, input().split())
MOD = 10 ** 9 + 7

def main():
    (n, p) = readline()
    a = sorted(readline())
    c = [0] * 32
    for (i, ai) in enumerate(a):
        v = ai
        while True:
            b = bisect(a, v, lo=0, hi=i)
            if b > 0 and a[b - 1] == v:
                break
            r = v % 4
            if r == 2 or v < a[0]:
                c[ai.bit_length()] += 1
                break
            elif r == 0:
                v //= 4
            else:
                v //= 2
    x = y = 0
    ans = 0
    for i in range(1, p + 1):
        z = ((c[i] if i < 32 else 0) + x + y) % MOD
        ans += z
        (x, y) = (y, z)
    print(ans % MOD)
if __name__ == '__main__':
    main()