Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def countSubsequences(a, n, p):
- dp={}
- '''
- We shall create a dp of size K*N k is given product.
- Each cell (x,y) in dp tells that how many subsequences are possible whose
- product <=k by choosing first y elements
- '''
- def help(i,cur):
- if cur==0 or i<0:return 0
- if (i,cur) in dp:return dp[(i,cur)]
- ans=0
- '''
- cur:current product
- i:first i elements of array a
- Now we are taking all the subsequence of previous cell
- since these are also the answers. And we shall add
- more subsequence if we found something new
- '''
- ans+=help(i-1,cur)
- if a[i]<=cur and a[i]>0:
- ans+=help(i-1,cur//a[i])+1
- '''
- We shall add 1 extra subsequence which is new {a[i]} .We shall add.
- Now we shall check the new subsequences with this a[i].
- so we shall compute (i-1,cur//a[i]). Here first parameter is i-1
- because we are computing it for first i vals of array.
- we shall count the subsequences of cur//a[i] that can be added to our a[i] and
- add this count to our answer
- '''
- dp[(i,cur)]=ans
- return ans
- return help(n-1,p)
Advertisement
Add Comment
Please, Sign In to add comment