题面很简洁，这里不做多说。
70pts 做法
首先考虑到 \(a_{n-1}\) 和 \(a_n\) 两项是整个数列 \(a\) 中的最大的两项，所以若 \(a_{n-1}+a_n\) 不超过 \(k+1\)，则数列中任意两项之和肯定不超过 \(k+1\)。
考虑当 \(a_{n-1}=x\) 时，首先可以计算出 \(a_n\) 的取值范围：
-
因为 \(a_{n-1}\leq a_n\)，故 \(a_n\geq x\)。
-
因为 \(a_{n-1}+a_n\leq k+1\)，则 \(a_n\leq k+1-x\)。
所以 \(x\leq a_n\leq k+1-x\)，取值数量为 \(k+2-2x\)，当 \(x > k+1-x\) 时取值数量为 \(0\)。
考虑第一个约束，因为：
\[1\leq a_1\leq a_2\leq ...\leq a_{n-2}\leq a_{n-1} \]将不等式的每一个部分加上下标，为了方便，下式的表达式所加的下标从 \(0\) 开始：
\[1\leq a_1+0 < a_2+1< ...< a_{n-2}+n-3 < x+n-2 \]所以 \(a_{n-2}+n-3\leq x+n-3\)。
具体证明本蒟蒻不太会，建议查询相关资料。
于是我们可以得到 \(a\) 数列的前 \(n-2\) 项就是在 \([1,x+n-3]\) 范围中选择 \(n-2\) 个数，方案数为 \({x+n-3\choose n-2}\)。
于是对于 \(a_{n-1}=x\)，方案数为 \({x+n-3\choose n-2}\times \max(k+2-2x,0)\)。
累加所有的可能，答案为：
\[\overset{k+1}{\underset{i=1}{\sum}} {i+n-3\choose n-2}\times \max(k+2-2i,0) \]100pts 做法
我们只需要化简如上求和式子即可，本蒟蒻不会等号对齐，故观感可能较差。
首先 \(\max(k+2-2i,0)\) 很难化简，于是我们需要求出 \(i\) 的上界，解不等式可得 \(\lfloor { \frac{k+1}{2} } \rfloor\)，为了之后化简的方便，以下用 \(m+1\) 代替该数字。
\[\overset{k+1}{\underset{i=1}{\sum}} {i+n-3\choose n-2}\times \max(k+2-2i,0) \]化为：
\[\overset{m+1}{\underset{i=1}{\sum}}{i+n-3\choose n-2}\times (k-2i) \]运用乘法分配律得：
\[k\times \overset{m}{\underset{i=0}{\sum}} {i+n-2\choose n-2} - 2\times \overset{m}{\underset{i=0}{\sum}} {i+n-2\choose n-2}\times i \]由组合数公式，得：
\[k\times {m+n-1\choose n-1} - 2\times \overset{m}{\underset{i=0}{\sum}} {i+n-2\choose n-2}\times i \]由于 \(\times 0\) 无意义，故省去，得：
\[k\times {m+n-1\choose n-1} - 2\times \overset{m}{\underset{i=1}{\sum}} {i+n-2\choose n-2}\times i \]变换形式，得：
\[k\times {m+n-1\choose n-1} - 2\times \overset{m}{\underset{i=1}{\sum}} \overset{i}{\underset{j=1}{\sum}} {i+n-2\choose n-2} \]调换求和顺序，得：
\[k\times {m+n-1\choose n-1} - 2\times \overset{m}{\underset{j=1}{\sum}} \overset{m}{\underset{i=j}{\sum}} {i+n-2\choose n-2} \]将第二个求和换成两式相减，得：
\[k\times {m+n-1\choose n-1} - 2\times \overset{m}{\underset{j=1}{\sum}} (\overset{m}{\underset{i=0}{\sum}} {i+n-2\choose n-2} - \overset{j-1}{\underset{i=0}{\sum}} {i+n-2\choose n-2}) \]运用组合数公式，得：
\[k\times {m+n-1\choose n-1} - 2\times \overset{m}{\underset{j=1}{\sum}} ({m+n-1\choose n-1} - {j-1+n-1\choose n-1}) \]拆除一个括号，方便化简，得：
\[k\times {m+n-1\choose n-1} - 2\times \overset{m}{\underset{j=1}{\sum}} {m+n-1\choose n-1} + 2\times \overset{m}{\underset{j=1}{\sum}} {j-1+n-1\choose n-1} \]化简第一个求和，得：
\[k\times {m+n-1\choose n-1} - 2m\times {m+n-1\choose n-1} + 2\times \overset{m}{\underset{j=1}{\sum}} {j-1+n-1\choose n-1} \]降低求和范围，得：
\[(k-2m)\times {m+n-1\choose n-1} + 2\times \overset{m-1}{\underset{j=0}{\sum}} {j+n-1\choose n-1} \]运用组合数公式，得：
\[(k-2m)\times {m+n-1\choose n-1} + 2\times {m+n-1\choose n} \]至此，我们就化简完毕，可以预处理阶乘及其逆元，求组合数时 \(\mathcal{O}(1)\) 求解，记得取余。
标签：underset,洛谷,P9035,题解,sum,times,leq,choose,overset From： https://www.cnblogs.com/ydzr00000/p/17093468.html