My guess would be write a function that can perform integer division between the string given and an integer using a standard algorithm. Then for each of the numbers j between 1 and 100 inclusive store the result of the division between the string given and j. Say the result is stored in an array called dp. Finally assume we have stored the q integers that they gave in an array called A. Set the ans to 0 then for each A[j] add dp[A[j]]+1 to the answer. Also you would have to take the modulo of results repeated throughout the whole process.

This is a 3 state dp problem where the states should be as follows:- (a) Index up to which str has been processed, (b) Value of the new str mod n and (c) Flag value z which stores whether a bit smaller than the bit str has been used or not till now. Overall complexity is (10000*100*2)*100 as there are 100 distinct possible mod values which will pass the time. Here is the AC Code : http://paste.ubuntu.com/24223122/

This problem could be solved with the natural approach involving a little bit of dynamic programming (basically memorization).

First, denote X as the decimal value of the bit-string. The number of bit-strings smaller than or equal to X which are divisible by n is simply the integer part of the division X / n, which is (X — r) / n, where r is the remainder part of the division X / n.

As we only need the answer in module MOD = 1000000007, we would need to compute X % MOD, r % MOD and 1/n % MOD (the inverse modulo of n in modulo MOD).

X % MOD could be computed in O(Nlog(N)), as X could be represented as a sum of power of 2, and each power of 2 can be computed in O(log(N)).

r % MOD is dependent on n. Thus for each n, we compute its r % MOD. This pre-computation takes O(Nn).

1/n % MOD is also computed for each n. This pre-computation takes O(nlog(MOD)).

Then, we can answer each query in O(1) time complexity with the formula (X — r) / n.

The overall complexity would therefore be O(q + Nlog(N) + Nn + nlog(MOD)), which is at most around 10^6 iterations.

You could also just use Python and preprocess all queries.