Count number of sequences of length n whose every adjacent elements product is less than or equal to p.
n <= 100
1 <= p <= 1e9
Testcases:
Input
p=3 , n=2
Output:
ans = 5
Explanation:
(1,1) , (1,2) , (2,1) , (1,3) , (3,1)
Other testcases
p=10, n=2
ans = 27
p=1, n=5
ans = 1
p=4, n=4
ans = 47
A key observation in this problem is that for any two adjacent numbers, one of them must be less than or equal to \sqrt{p}.
Then dynamic programming can be used. The state design is as follows. Let dp(i,j,f) denote the current i-th position from left to right, f=0 when the number in this position is j, while f=1 when the number in this position is in the interval (\lfloor\frac{n}{j+1}\rfloor,\lfloor\frac{n}{j}\rfloor]. It follows that j is about \sqrt{p}, and so the number of states is O(n\sqrt{p}).
As for the equation is slightly more complicated, each time to transfer from the previous position of a section of the interval, the also need to maintain each i corresponding to \sum_j dp(i,j,p), that is, the prefix sum.
Time Complexity: O(n \sqrt{p})