Number of solutions

Question

I am stuck on a problem,

  x1 + x2 + x3 +x4 +x5 + x6 < M

where xi's are positive integers and M can be any value from [1,6000000]. How many unordered solutions with distinct xi's exists. I want to know whether this can be done by dynamic programming( with it running fast with the given constraints and within memory limits) , or I have to come up with a combinotorics formula.
I have to report the answer modulo 1000000007
PS: I don't want the solution

Answer 1

You don't want the complete solution, so I won't give it to you; I'll just try to point you in the right direction.

First of all, you need to decompose the problem in simpler ones. In your case, this do the trick:

|(x_1,...x6) : sum(x_i) < M | = sum( |(x_1,...,x6) : sum(x_i) = N|)

for N=6,...,M-1 . Now, you only need different solutions, so you can assume that:

x_1 <= x_2 <= ... <= x_6

Now, counting the number of ways you can get k elements to sum up to N isn't that hard ( try first with 2 elements, than 3, and try to get the general forumla and, if you have some time on your hands, prove it by induction ), and once you have that you are basically done.

IMPORTANT NOTE : as it should be clear by now, I think that the combinotorics approach is way better than the brute force one

Answer 2

You can go brute force, just create a vector (or other dynamic container ) to push solution while you go. This will not be a memory problem. but this will be long to process. Another idea is to create a fstream, and flush regularly (every 10000 solution);