### tzc___wk's blog

By tzc___wk, history, 9 months ago,

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?

• -3

 » 9 months ago, # |   0 Auto comment: topic has been updated by juruo_tzc (previous revision, new revision, compare).
 » 9 months ago, # |   -14 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 ) . Code int n; cin>>n; int a[n]; for(int i = 0 ; i < n; ++i) cin>>a[i]; int N; // The sum we want to make . cin>>N; int dp[N+1]; memset(dp , 0 , sizeof dp); dp[0] = 1; sort(a , a + n); for(int i = 0 ; i < n ;++i){ for(int j = N ; j >= a[i] ; --j) dp[j]+=dp[j-a[i]]; } cout<
•  » » 6 months ago, # ^ |   +9 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?
•  » » » 6 months ago, # ^ |   -10 stO tzc Orz
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -27 At the time when I commented the constraints were not mentioned so I suggested this.
•  » » » » 5 weeks ago, # ^ |   0 Actually it was
 » 6 months ago, # |   0 Auto comment: topic has been updated by tzc___wk (previous revision, new revision, compare).
 » 6 months ago, # |   -16 By Wikipedia, it is NP problem
 » 6 months ago, # | ← Rev. 2 →   -6 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.
 » 5 weeks ago, # | ← Rev. 3 →   +18 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.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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