### tzc___wk's blog

By tzc___wk, history, 6 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

 » 6 months ago, # |   0 Auto comment: topic has been updated by juruo_tzc (previous revision, new revision, compare).
 » 6 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<
•  » » 2 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?
•  » » » 2 months ago, # ^ |   -10 stO tzc Orz
•  » » » 2 months ago, # ^ | ← Rev. 2 →   -27 At the time when I commented the constraints were not mentioned so I suggested this.
 » 2 months ago, # |   0 Auto comment: topic has been updated by tzc___wk (previous revision, new revision, compare).
 » 2 months ago, # |   -16 By Wikipedia, it is NP problem
 » 2 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.