Hello,

I want to ask for an idea to solve this problem:

Given N <= 10^9 and K <= 5. How many sets (a1, a2, ..., ak) that 1 <= a1 < a2 < a3 < ... < ak <= N and a1 + a2 + ... + ak = N?

For an example, with N = 10, K = 3, the result is 4: (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5).

Thanks!

Nvm, I misread the problem.

For the above example (N = 10, K = 3). By your idea, the number of sets will be equal with the number of the solutions of X1 + X2 + X3 + X4 = 13 (which is equal 220)?? Am I wrong anywhere? Thanks!

But every element should be unique in this problem. Stars and bars does not consider this. Can you please explain how will your solution ensure uniqueness?

Very similar to an ongoing contest problem.

Oops, my bad. I should have checked before commenting. At least I misread the question and failed to solve it correctly lol.

Can you give me the link to this contest? Please!

Yeah sure, after the contest ends, I'll send you the link.

Hope it's not a month-long contest — would like to check it out.

https://math.stackexchange.com/questions/1866682/how-many-length-k-strictly-decreasing-sequences-where-sum-is-n

Thank you. I've read it but in my problem, N is so large (about 10^9) so I don't think dynamic programming will be useful. And I think both solutions in your link can't be optimized by matrix mul :((. Are you have any idea?

https://math.stackexchange.com/questions/999319/how-solutions-of-distinct-non-negative-solutions-are-there-to-k-1-cdotsk-n-k divide by number of permutations

Also https://math.stackexchange.com/questions/1002344/number-of-positive-integral-solutions-to-xyzw-20-with-xyzw-and-x-y-z?noredirect=1&lq=1

No wonder you diss the dynamic programming approach, hater.

Because I'm bad at dynamic programming lol.

I am not sure it is correct approach or not. Here K is very small so we can brute force for each i<=K. A

_{1}+A_{2}+A_{3}+..+A_{k}=N For this equation find the positive integer solution.StackExchangehttps://math.stackexchange.com/questions/919676/the-number-of-integer-solutions-of-equations

This solution contains duplicates(A

_{i}=A_{j}for i!=j) so we have to eliminate that duplicates.I can suggest the following approach. Let's convert the condition $$$1 \le a_1 \lt a_2 < a_3 < \dots < a_k \le N$$$ to more friendly one. For this we introduce new variables $$$b_i$$$ with relations $$$a_1 = 1 + b_1; a_2 = 1 + a_1 + b_2 = 2 + b_1 + b_2; a_3 = 1 + a_2 + b_3 = 3 + b_1 + b_2 + b_3$$$ and so on. So we can rewrite our original equation $$$a_1 + a_2 + \dots + a_k = N$$$ as $$$kb_1 + (k-1)b_2 + \dots + b_k = N - \frac{k(k+1)}{2}$$$ with the only conditions $$$b_i \ge 0$$$. For example, if $$$k$$$ is 4 we have the linear diophantine equation

where all $b_i$ (I mean $$$b_i$$$) are nonnegative. It is also evident that if $$$N \lt 10$$$ we have no solutions to the equation.

We can find the number of nonnegative solutions of some linear diophantine equation with the help of generating function. For our example generating fuction is

or

or

or

or

Now you can use matrix exponentiation. Your goal is $G_{N-10}$. I mean $$$G_{N-10}$$$. Also you can precalculate all coefficients, initial values and matrices.

PS Here are some errors in math processing, sorry.

PPS You can find the direct formulae for cases $$$k = 2,3,4$$$ on this page.

Can you explain more about generate function and using it to count non-negative solutions of Diophantine equation? Please!

A generating function is a way of encoding an infinite sequence into a function. Let $$$G(<a_n>; x)$$$ be the ordinary generating function (OGF) of the sequence $$$<a_n>$$$. Then, $$$G(x) = \sum_{i=1}^{\infty} a_i x^i$$$.

Consider the function $$$g(x)=(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)(1+x^4+x^8+...)$$$. Each term (say $$$x^j$$$) in the expansion of $$$g$$$ represents a distinct way of getting the power $$$j$$$ on $$$x$$$ by choosing 4 terms, one of each bracket series. Much like one of the solutions of $$$b_4 + 2b_3 + 3b_2 + 4b_1 = j$$$.

Thus, in the expansion of $$$g$$$, we have exactly one $$$x^j$$$ for each way to get sum $$$j$$$. Thus, the coefficient of $$$x^j$$$ in the standard form the expansion will be the number of solutions for $$$b_4 + 2b_3 + 3b_2 + 4b_1 = j$$$. Can you see how $$$g$$$ is the OGF of our answer sequence? ($$$<z_n>$$$ where $$$z_{N-10}$$$ is our answer).

The expression can be rewritten as $$$((1−x)(1−x^2)(1−x^3)(1−x^4))^{-1}$$$ (The infinite geometric sum property). So we need to find the coefficient of $$$x^{N-10}$$$ in this. The above comment by feodorv continues from here.

Hope this gave you new insight.

Here are some GF blogs, blog_1, blog_2, and the blog that I picked them up from, blog_0.

Misinterpreted the problem, Sorry.

Downvotes are really an eyeopener

Yep. Thought "answer is simply (n-k+1)C(k-1)" doesn't even correspond to test answer.

UPD: Nvm read the problem wrong.

Ignore.Use recursion, Let n be the number of identical things to be distributed among r identical boxes with base cases:

1) n<r : 0

2) n=r : 1

3) n=r+1 : 1

4) r=1: 1

5) r=2: floor(n/2)

And now use recursion: dp(n,r) = (from k=1 to r) ∑ dp(n−r,k)

I like your username. I think in your case hate=love. Right ?

Your comments give me brain tumor

Just seen this today, we will use digit DP to solve this. Let $$$t$$$ denote the number of digits of $$$n$$$ .We have to build $$$k$$$ numbers so that:

WLOG, let's assume that $$$x_1 < x_2 < ... < x_k$$$

$$$f(i, carry, comp, ok)$$$ is the number of ways to build the answer at $$$i$$$ where:

$$$carry$$$ is the carry number from last column. $$$k≤5$$$ so $$$carry≤4$$$

$$$comp$$$ is a mask. $$$ith$$$ bit of $$$comp$$$ is $$$1$$$ only if there is $$$j < i$$$ that $$$x[i][j] < x[i + 1][j]$$$

$$$ok$$$ is $$$true$$$ if $$$x_1$$$ already bigger than 0

Pseudo-code

The complexity is $$$O(t * 4 * 10^k * 2^k)$$$

I have edited a few things, my fault. Here is my implementation of above formula (The code was accepted yay).

Bonus:Working with base 2 will considerably reduce time complexity (only $$$O(32 * 10 * 4^k)$$$). So $$$k = 10$$$ is achievable!And hope you would love DP from now on ^^

Thanks so much!! Your solution is so amazing!