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 rlajkalspowq (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 ) .
This 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.
Actually it was
Auto comment: topic has been updated by rlajkalspowq (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.
There is an $$$O(N + S log(S))$$$ algorithm for subset sum using "polygon" $$$ln$$$ and $$$exp$$$ explained in this paper ( https://arxiv.org/pdf/1807.11597.pdf ) and in the editorial for this CodeChef Long Challenge problem ( https://www.codechef.com/JUNE20A/problems/PPARTS ). The CodeChef problem is, as expected, a much more complicated version of the subset sum problem, but the same ideas that solve that problem can be used to solve your problem (yours is a special case where $$$b_i = 1$$$).
For non-NTT friendly modulos like your $$$10^9 + 7$$$, you can compute convolutions modulo three different NTT-friendly primes and combine with CRT, or use Karatsuba instead of NTT (see problem https://judge.yosupo.jp/problem/convolution_mod_1000000007 ).
For the subset sum problem, you can also take a look at the solutions for ( https://judge.yosupo.jp/problem/sharp_p_subset_sum ). The problem here uses NTT-friendly modulo, though.
Hi there is one question find minimum number of a_i that sum = S, or -1 if not possible how to solve that
Also we can take any number of copies of a_i,
But constraints are very high like a_i ,n,S<=10^6
Someone asked me this question on telegram. But I am stuck on it from many days and I could not think of any approach,
I also referred this interesting codeforces blog but still stuck link
I also tried each a_i in powers of 2 but dp seems too costly, is there any greedy solution to this question.
P.S- please forgive me for posting this here