Find the total number of distinct Non decreasing a

问题:

Given the exact no. of elements that must be present in the array (let=r) and the max value of the last element of the array (let=n) find the total number of distinct non decreasing arrays possible (all elements of array must be >=0)

Example- If r=3 and n=2 then some possible non decreasing arrays are {0,0,2},{0,0,1},{0,0,0},{1,2,2} etc. I need the no. of these kind of arrays possible.

I tried to solve it using recursion and memoization but it is too slow.

here is my code (ll means long long)-

ll solve(ll i,ll curlevel)
{
    if(dp[i][curlevel]!=-1)
        return dp[i][curlevel];
    if(i<0)
        return dp[i][curlevel]=0;
    if(curlevel==r)
        return dp[i][curlevel]=1;
    if(curlevel>r)
        return dp[i][curlevel]=0;
    ll ans=0;
    for(ll k=i;k>=0;k--)
    {
        ans+= solve(k, curlevel+1);
    }
    return dp[i][curlevel]=ans;
}

I call this function as follows.

for(ll i=n;i>=0;i--)
    {
        res+=solve(i, 1);
    }

I am looking for a faster way to do this.

回答1:

Let's take some non-decreasing sequence which qualifies, and encode it using 0s and 1s. The decoding algorithm is simple:

• Set the_value to 0
• For each element in the coded sequence:
  • If the element is 0, output the_value.
  • If the element is 1, add 1 to the_value.

Now, I claim that any non-decreasing sequence can be encoded with a sequence of exactly r 0s (because we need to output exactly r values) and n 1s (because we cannot exceed the value n), and every such coded sequence corresponds to a unique non-decreasing sequence. (The encoding algorithm and the proof of bijection are left as exercises.)

So the number of uncoded sequences is the same as the number of coded sequences. But the number of coded sequences is simply the number of ways of choosing r positions to insert a 0 from the n+r positions in the coded sequence. Hence the number of possibilities is n+r choose r, or (n+r)!/(n!*r!).

These numbers grow rapidly, and you will need bignum arithmetic to compuate them for even moderately sized r and n. For example, if n and r are both 2000, then the count of sequences is a number with 1203 digits, approximately 1.66 * 10¹²⁰².

Obviously, it is futile to attempt to enumerate a set of sequences of this size. For small values of r and n, the sequences can be enumerated in amortized time O(1) per sequence, using the standard lexicographical enumeration algorithm, which takes a sequence and produces the next sequence in lexicographical order:

1. Find the rightmost element of the sequence which can be made larger. (In this case, find the rightmost element of the sequence which is not equal to n.) If there is no such element, all sequences have been enumerated.

2. Advance the element which has been found. (In this case, add 1 to the element.)

3. Set all subsequent elements (if any) to their smallest possible values. (In this case, set all subsequent elements to the new value of the element found in step 1.

回答2:

not for the added part: It boils down to the combinations with repetition allowed in non-descendign order. For n we have 0-n symbols (i.e. n+1 symbols) and r the length. With this in mid and this answer on math.stackexchange we get a simple formula: