I sincerely hope, that this question does not belong to any ongoing contest : D @aryanc403 If it does, please don't answer this question :) We are given integers,namely, a,b,c and d. Also, 0<=a,b,c,d<=1000 We have to satisfy this equation : a+b^2+c^3+d^4<=S, where , 0<=s<=10^18 We will be given an integer, 'S' as the input. We have to find the no. of integral solutions which satisfy the above equation!:) I know the bruteforce way, can anybody propose a nice dpway to solve it? Thanks. Link to the sequence :> https://oeis.org/search?q=1%2c4%2c7%2c8%2c9%2c11%2c12%2c12&fmt=data asked 20 Jan, 23:59

I think no need of DP, for all $c,d<=1000$ find out all values of $c^3+d^4$ there will be around $10^6$ values, store them and sort that array ($A$). Now for each $a,b$ find out all possible values of $a+b^2$ similarly call it array $B$ now for each element $B[i]$ of $B$ do binary search on $A$ and find count of all values such that $A[i][+B[j]<=S$ , so add $j$ to $ans$ each time. answered 21 Jan, 00:18
2
Thankyou so much :) I awarded you some of my reputation points. Stay blessed :)
(21 Jan, 00:32)
2
Recently, I came across the above technique due to E. Helping Hiasat it is known as meet in middle.
(24 Jan, 06:55)

Note: Is there a way other than dp to solve it, like some formula?