### no_life's blog

By no_life, history, 9 months ago, ,

We all know that the number of solutions to a+b = 3 (where a and b are non negative) can be easily found out by stars and bars theorem. So answer of the above is 4. { (3,0),(0,3),(1,2),(2,1)}. But I want the answer to be 2 as the first two and last two are equivalent. Formally, as the stars and bars give the number of ordered sets, I want to find out the number of unordered sets.

•
• -13
•

 » 9 months ago, # |   0 Number of ordered sets ((a+b)/2)+1 if i understood your question correctly.
 » 9 months ago, # | ← Rev. 2 →   +5 This can be solved by dynamic programming the general case. First of all define P(N,K) as the number of ways you can represent N using K numbers in ascending order.Now for solving P(N,K), if K > N then answer is 0, otherwise let's distribute 1 item on each set. Your task is now to distribute N — K items without breaking the ascending order.If you place an item, in the ith set, you must use n — i — 1 items for later sets to compensate. So you can just apply dynamic programming and solve it O(N*K).
•  » » 9 months ago, # ^ |   0 N is up to 1e9. Can we use prime factors of N to solve this?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   0 Can you post the problem link?
»
9 months ago, # |
+8

# ?detaR tI sI

 » 9 months ago, # |   0 I'm gonna take a guess and say that you are looking for the partitions of a number. https://en.wikipedia.org/wiki/Partition_(number_theory) You can check here for fancy formulae, or just look for a dp solution :)
•  » » 9 months ago, # ^ |   0 InputN = 64, K = 3Output7This can be expressed as a product of three integers in the following ways:1 x 1 x 641 x 2 x 321 x 4 x 161 x 8 x 82 x 2 x 162 x 4 x 84 x 4 x 4Therefore, 7 ways.