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.

Number of ordered sets ((a+b)/2)+1 if i understood your question correctly.

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).

N is up to 1e9. Can we use prime factors of N to solve this?

Can you post the problem link?

## ?detaR tI sI

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 :)

Input

N = 64, K = 3

Output

7

This can be expressed as a product of three integers in the following ways:

1 x 1 x 64

1 x 2 x 32

1 x 4 x 16

1 x 8 x 8

2 x 2 x 16

2 x 4 x 8

4 x 4 x 4

Therefore, 7 ways.