You're given $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, you need to count the number of ways to choose some of them (no duplicate) to make the sum equal to $$$S$$$. Print the answer in modulo $$$10^9+7$$$. How to solve this problem in polynomial time?

Note: The $$$n,S$$$ can be as large as $$$10^5$$$ so using single DP can't work. Using polygon $$$ln$$$ or $$$exp$$$ might work. But I don't know how to use them (I've just heard of it). Can anyone explain it?

Auto comment: topic has been updated by juruo_tzc (previous revision, new revision, compare).I think this should work . let's make a dp array where dp[i] = no. of ways to make sum i .

Now we don't want to repeat our items so we are going to iterate from the end of sum .

For more info watch Errichto DP tutorial 2 . (Well actually I don't remember the exact number but I think it's 2 ) .

CodeThis is actually $$$\mathcal O(n^2)$$$. What if $$$n=10^5$$$

I think it can be solved using polygon $$$ln$$$ and $$$exp$$$. (I've just heard of it and don't know how to use). Can anyone explain it?

stO tzc Orz

At the time when I commented the constraints were not mentioned so I suggested this.

Auto comment: topic has been updated by tzc___wk (previous revision, new revision, compare).By Wikipedia, it is NP problem

You can use a observation that if S <=10^5, then there can be atmax O(sqrt(S)) different value of elements in the array. You can batch process each value together to get a O(S*sqrt(S)) complexity.