「KDOI-04」Pont des souvenirs 题解

· · 题解

做法 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 的值，分为两种情况：

即：

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