tzc___wk's blog

By tzc___wk, history, 6 months ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by juruo_tzc (previous revision, new revision, compare).

»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tzc___wk (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it -16 Vote: I do not like it

By Wikipedia, it is NP problem

»
2 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

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.