Iterated Bitcount Function
All submissions for this problem are available.
Let f(x) be the number of 1's in the binary representation of x. We can define f^k(x) as f(x) for k = 1, and f^(k-1)(f(x)) for k > 1. Let f^*(x) be the smallest k >= 1 such that f^k(x)=1.
Given N and K, how many numbers x between 1 and N inclusive have f^*(x) = K ?
The first line contains the number of test cases T. Each of the next T lines contains two space separated numbers N and K.
Output one line corresponding to each test case, containing the answer for the corresponding test case. Output all answers modulo 1000000007.
Input 6 1 1 2 1 3 1 3 2 13 3 20 2 Output 1 2 2 1 3 10
|Time Limit:||0.345622 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, PYTH 3.6, PYPY, GO, NODEJS, rust, swift, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.