自动搬运

查看原文

来自洛谷，原作者为

	Polaris_Australis_ AFOed

搬运于2025-08-24 22:44:48，当前版本为作者最后更新于2023-02-04 22:05:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

做法 1

暴力枚举，复杂度 $O(k^n)$。

做法 2

容易发现，$k=1$ 时答案为 $1$，$k=2$ 时答案为 $2$，$k=3$ 时答案为 $n+2$。

做法 3

设 $dp_{i,j}$ 表示到 $i$ 位置为止最大数为 $j$ 的方案数，$dp_{i,j}=\sum\limits_{l=1}^{j}dp_{i-1,l}$，复杂度 $O(n\times k^2)$，前缀和优化即可 $O(n\times k)$，最后一位上界为 $k$，其余位上界为 $\lfloor\frac{k+1}{2}\rfloor$。

做法 4

根据上边的 dp 式矩阵乘法，复杂度 $O(k^3\log_2n)$。

做法 5

设 $a_0=1$，对于 $1\le i\le n$，$b_i=a_i-a_{i-1}$。枚举 $a_n$ 的值，分为两种情况：

1. $a_n\le\lfloor\frac{k+1}{2}\rfloor$，则不需要考虑题目中第二条限制，所以只需要求满足 $(\sum\limits_{i=1}^{n}b_i)=a_n-1$ 的方案数即可，即可重组合数 $H_{n}^{a_n-1}=\binom{n+a_n-2}{a_n-1}$。
2. $a_n>\lfloor\frac{k+1}{2}\rfloor$，此时要考虑第二条限制，即 $a_{n-1}\le k+1-a_n$，容易发现，这一条件等价于最后一位为 $k+1-a_n$ 的方案数，于是转化为第一种情况。

即：

$$ans=\sum\limits_{i=1}^{\lceil\frac{k}{2}\rceil}\binom{n+i-2}{i-1}+\sum\limits_{i=1}^{\lfloor\frac{k}{2}\rfloor}\binom{n+i-2}{i-1} $$

复杂度 $O(k)$。

做法 6

首先有一个组合数求和结论：

$$\sum\limits_{i=l}^{r}\binom{i}{k}=\binom{r+1}{k+1}-\binom{l}{k+1} $$

证明的话直接移项，然后一直根据递推式合并即可。

之后利用这个结论去推式子：

$$\begin{aligned} ans&= \sum\limits_{i=1}^{\lceil\frac{k}{2}\rceil}\binom{n+i-2}{i-1}+\sum\limits_{i=1}^{\lfloor\frac{k}{2}\rfloor}\binom{n+i-2}{i-1}\\ &=\sum\limits_{i=1}^{\lceil\frac{k}{2}\rceil}\binom{n+i-2}{n-1}+\sum\limits_{i=1}^{\lfloor\frac{k}{2}\rfloor}\binom{n+i-2}{n-1}\\ &=\binom{n+\lceil\frac{k}{2}\rceil-1}{n}+\binom{n+\lfloor\frac{k}{2}\rfloor-1}{n} \end{aligned} $$

总复杂度 $O(\max(n+\lceil\frac{k}{2}\rceil)+T)$。