PROBLEM LINK:
Author: Subham Das
Tester: Soumik Sarkar
Editorialist: Soumik Sarkar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary representation, Ad hoc
PROBLEM:
Given a sequence 7, 11, 13, 14, 19… the problem is to find the kth number of the sequence modulo 109+7.
EXPLANATION:
The sequence is the list of all numbers with 3 set bits in their binary representation, in ascending order. How do we realize this? If not by observation, plugging the sequence into the OEIS (On-line Encyclopedia of Integer Sequences) is always helpful. In addition to the given first 5 terms, we also know that the 8th term is 25 and the 12th term is 37 from the sample input and output. So, if we search for “7, 11, 13, 14, 19, _, _, 25, _, _, _, 37” on the OEIS, we get sequence A014311, which tells us the logic behind the sequence.
The sequence can also be said to be of those numbers which are the summation of exactly three disinct powers of two. Our approach is to precompute results for all possible queries 1 ≤ k ≤ 106. For this we also need to precompute powers of 2 modulo 109+7. We know that there are \binom{n}{3} ways of choosing 3 distinct elements out of n elements. Thus, precomputing 183 powers of 2 is enough, because \binom{183}{3} = 1004731, which is just greater than 106, the maximum possible value of k. The algorithm is shown below
pow2 = array of size 183
pow2[0] = 1
for i in [1..182]
pow2[i] = pow2[i-1] * 2
pow2[i] = pow2[i] % 1000000007
Next we use 3 nested loops to iteratively calculate the terms of the sequence.
f = empty list
for i in [2..182]
for j in [1..i-1]
for k in [0..j-1]
term = pow2[i] + pow2[j] + pow2[k]
term = term % 1000000007
append term to the end of f
Then for each input k, the output is the corresponding value from the f array.
Complexity of this approach:
Precomputation requires \mathcal{O}(max\ k).
Each test case query requires \mathcal{O}(1).
ALTERNATE SOLUTION:
An alternate approach is to use the HAKMEM item 175 to generate consecutive terms of the series starting from 7. The program to generate the series provided in OEIS A014311 uses this method. However, one would need to use big integer types to solve the problem by this approach.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.