给出确切的编号。数组中必须存在的元素（let = r）和数组最后一个元素的最大值（let = n）的总和，找出可能的不同非递减数组总数（数组的所有元素必须> = 0 ）
示例-如果r = 3和n = 2，则一些可能的非递减数组为{0,0,2}，{0,0,1}，{0,0,0}，{1,2,2}等。我需要没有 这些阵列的可能性。
我试图使用递归和记忆来解决它，但是它太慢了。
这是我的代码（ ll表示很长很长 ）-
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; }
我称这个功能如下。
for(ll i=n;i>=0;i--) { res+=solve(i, 1); }
我正在寻找一种更快的方法。
让我们采用一些非递减序列进行限定，并使用0和1对其进行编码。解码算法很简单：
现在，我声称 任何 不递减的序列都可以用正好为r0（因为我们需要输出准确的r值）和n1（因为我们不能超过value n）的序列进行编码，并且每个这样的编码序列都对应于唯一的非递减顺序。（编码算法和双射证明留待练习。）
r
n
因此，未编码序列的数量与编码序列的数量相同。但是，编码序列的数量仅仅是r从n+r编码序列中的位置中选择插入0的位置的方式的数量。因此，可能性的数量是n+rselect r或(n+r)!/(n!*r!)。
n+r
(n+r)!/(n!*r!)
这些数字迅速增长，您将需要BIGNUM算术compuate他们甚至中等规模的r和n。例如，如果n和r均为2000，则序列数是一个具有1203个数字的数字，大约为1.66 * 10 1202。
显然，尝试枚举此大小的序列集是徒劳的。对于小值r和n，该序列可以在每个序列分期时间O（1）列举，使用标准辞书枚举算法，这需要一个序列，并产生在词典编纂顺序的下一个序列：
找到可以放大的序列中最右边的元素。（在这种情况下，找到不等于的序列的最右边元素n。）如果没有这样的元素，则已枚举所有序列。
前进已找到的元素。（在这种情况下，将1加到元素上。）
将所有后续元素（如果有）设置为最小的值。（在这种情况下，请将所有后续元素设置为在步骤1中找到的元素的新值。
