I think the brute-force solution may work. Any judge to submit?

Here, since input size is less than or equal to 1000, we can just consider all the subsequences and find the product of each of them. For example, we fix a left point on the array, and for that keep extending the right endpoint, unless we exceed K. The number of times we can shift the right endpoint is the number of possible right endpoints if the left endpoint is fixed at the index where we had initially done. Now, just iterate over all possible left endpoints.

complexity: o(n^2).

A better solution would be to use a 2 pointer type algorithm. Here, observe that if we already have a subsegment whose product exceeds K, then if we multiply more elements, it will still always exceed K. Thus, we need to divide some previous elements first. So to do this, start the left and right endpoints at 0. Then keep moving the right endpoint and keep multiplying the new elements. Each time you are able to do so without exceeding K, increase ctr. Now, if the product exceeds K, then start shifting the left endpoint and divide the product that you had, with the element the left endpoint is processing, until the product again becomes lesser than K. Now, again start shifting the right endpoint and increasing ctr as before.

complexity: o(n) [since the right endpoint shifts at most n times and so does the left.]

Good day to you,

Well, since the K is pretty low, the easiest approach might (imho) be 2D Dynamic Programming, where first dimension is index of array and second is product. In each DP-state you either try to "multiply" by current number or simply go to next-number.

In recursive form, it might look like:

dyn (I k)
   if I == N: return 1
   if k >= K: return 0
   return dyn(I+1,k)+dyn(I+1,k*A[I])

I guess some memorisation + some modulo (etc.. sauce) will be necessary, yet I'm sure you'll deal with it.

Good Luck & Have Nice Day!

Let z be the number of zeros in the array and n be the total number of elements. There are (2^z - 1)·2^n - z subsequences with product 0. Remove all zeros now and operate on the remaining array.

We do something similar to what -Morass- described. Let small(i, j) denote the number of subsequences of the first i elements with product at most j. It's a simple DP, but we do this only for . Likewise, define large(i, j) such that the product is required to be at most . Again, we do this for .

It's easy to deduce the following formulas now:

The final answer large(n, 1) is obtained in time.

I tried to implement this: Code. Just tested on your samples and only for small answers (no modulo).