由于没有确切的。元素必须是present阵列中的（让= r）和所述阵列的最后一个元素的最大值（让= n）的发现不同的非递减阵列可能的总数（数组的所有元素必须是> = 0）

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)

例 - 当R = 3和n = 2那么一些可能的非递减数组是{0,0,2}，{0,0,1}，{0,0,0}，{1,2,2 } 等等。 我需要的没有。对这类阵列成为可能。

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.

这是我的code（ LL意味着很长很长） -

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.

推荐答案

让我们采取一些非递减序列，其资格，并设有code。使用0和1的。解码算法很简单：

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

设置the_value 0 对于在codeD序列中的每个元素： 如果该元素为0，输出the_value。 如果该元素是1，加1 the_value。 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.

现在，我主张的任意的非递减序列可以连接codeD用恰好研究 0的顺序（因为我们需要输出完全研究值）和 N 1秒（因为我们不能超过该值ñ ），而该等codeD序列对应唯一的一个非递减序列。 （编码算法和双射的证明被留下作为练习。）

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

所以未codeD序列的数量是相同的codeD序列的数量。但是，codeD序列号是简单的选择方法研究职位的人数插入0从ñ+ R 在codeD序列位置。因此可能性的数量是ñ+ R 选研究或（N + R） ！/（N！* R！）。

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

这些数字迅速增长，您将需要BIGNUM算术compuate他们甚至中等规模的研究和 N 。例如，如果 N 和研究都是2000，那么序列的计数是一个数字与1203的数字，大约1.66 * 10 1202 。

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 * 101202.

显然，这是徒劳的尝试列举一组这种规模的序列。对于较小的值研究和 N ，该序列可以分期时间Ø枚举（1）每个序列，使用标准辞书枚举算法，这需要一个序列，并产生下一个顺序的字典顺序：

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:

查找它可以更大的序列的最右边的元件。 （在这种情况下，发现该序列的最右边的元件，其不等于 N 。）如果不存在这样的元件，所有的序列都被枚举

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.

进展已经发现的元素。 （在这种情况下，添加1到的元素。）

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

设置所有后续元素（如果有的话），以它们的最小可能值。 （在这种情况下，将所有后续元素在步骤1中找到的元素的新值

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.