P9035 题解

· · 题解

P9035 题解

建议在博客里食用：

题目链接

题目描述

给定正整数 n,k，求有多少个长度为 n 的正整数序列 a 满足：

答案对 10^9+7 取模。

前置知识

组合数，推式子。

简要分析

我们看第二个约束，再结合第一个大小关系的约束，不难得到数列只需满足约束一以及满足 a_{n-1}+a_n\le k+1 即可。

可以考虑枚举 a_{n-1} ，分别计算出 \{a_1,a_2,\cdots,a_{n-2}\} 这一段的数量以及 a_n 的数量，最后乘一下再加起来即可。

同时也要注意 a_{n-1} 的范围。由 0<a_{n-1}\le a_n\le k 及 a_{n-1}+a_n\le k+1 易得 0<a_{n-1}\le\lfloor\frac k 2\rfloor。

接着是 a_n 的数量。当 a_{n-1}=i 时，可得 a_n\in[i,k+1-i]，所以它的数量为 (k-2i+2)。

只需再考虑前半段即可。

深度思考

对于 \{a_1,a_2,\cdots,a_{n-2}\} 的数量，我们拎出来化作这样一个问题：

给定 n,m，求长度为 n 的整数序列 \{a\} 的数量，使得 0<a_1\le a_2\le\cdots\le a_{n-1}\le a_n\le m。

对于这个问题，考虑 dp。记 f[i][j] 为 0\le a_1\le a_2\le\cdots\le a_{i-1}\le a_i=j 的方案数，容易得到转移方程：

f[i][j]=\sum_{k=1}^j f[i-1][k]

其中，边界条件为 f[i][1]=1,f[1][j]=1。

答案为 \sum\limits_{j=1}^m f[n][j]=f[n+1][m]。

再对方程进行研究：

\begin{aligned}f[i][j]=&\sum_{k=1}^j f[i-1][k]\\=&\left(\sum_{k=1}^{j-1}f[i-1][k]\right)+f[i-1][j]\\=&f[i][j-1]+f[i-1][j]\end{aligned}

得到了它的直接递推式，现在我们考虑它的通项公式。

可以证明，它的通项公式为 f[i][j]={\rm C}_{i+j-2}^{i-1}。可以用数学归纳法证明。

于是我们得出结论：若记答案为 \rm ans，那么：

{\rm ans}=\sum_{i=1}^{\lfloor\frac{k+1}2\rfloor}(k-2i+2)f[n-1][i]=\sum_{i=1}^{\lfloor\frac{k+1}2\rfloor}(k-2i+2){\rm C}_{n+i-3}^{n-2}

若组合数的求解为 \mathcal O(1)，那么该算法单次复杂度为 \mathcal O(k)，可以有 \rm 70pts。

推式子

我们给出两个将要用到的恒等式：

\boxed{\sum_{k=0}^n{\rm C}_{k}^m={\rm C}_{n+1}^{m+1}} \boxed{n{\rm C}_ {n-1}^{m-1}=m{\rm C}_n^m}

证明过程在文末参考资料。

为了让文章详略得当， 直接给出推式子的简单过程以及结果，详细讲解见云剪切板。

\begin{aligned} {\rm ans}=&\sum_{i=1}^{\lfloor\frac{k+1}2\rfloor}(k-2i+2){\rm C}_{n+i-3}^{n-2}\\=&\sum_{i=0}^{\lfloor\frac{k+1}2\rfloor-1}(k-2i){\rm C}_{n+i-2}^{n-2}\\=&\sum_{i=0}^{\lfloor\frac{k+1}2\rfloor-1}\Big[(k+2n-2){\rm C}_{n+i-2}^{n-2}-2(n+i-1){\rm C}_{n+i-2}^{n-2}\Big]\\=&\left[(k+2n-2)\sum_{i=0}^{\lfloor\frac{k+1}2\rfloor-1}{\rm C}_{n-2+i}^i\right]-2\sum_{i=0}^{\lfloor\frac{k+1}2\rfloor-1}(n+i-1){\rm C}_{(n+i-1)-1}^{(n-1)-1}\\=&(k+2n-2){\rm C}_{n+\lfloor\frac{k+1}2\rfloor-2}^{\lfloor\frac{k+1}2\rfloor-1}-2\sum_{i=0}^{\lfloor\frac{k+1}2\rfloor-1}(n-1){\rm C}_{n+i-1}^{n-1}\\=&(k+2n-2){\rm C}_{n+\lfloor\frac{k+1}2\rfloor-2}^{n-1}-2(n-1)\sum_{i=0}^{\lfloor\frac{k+1}2\rfloor-1}{\rm C}_{n-1+i}^i\\=&(k+2n-2){\rm C}_{n+\lfloor\frac{k+1}2\rfloor-2}^{n-1}-2(n-1){\rm C}_{n+\lfloor\frac{k+1}2\rfloor-1}^n\end{aligned}

得到了这个式子后，我们就能单次 \mathcal O(1) 求解啦。

当然，不要忘了 \mathcal O(1) 组合数的实现需要线性处理出阶乘及其逆元。

总时间复杂度 \mathcal O(\max\{n+\lfloor\frac {k+1} 2\rfloor\}+\log p+T)，空间复杂度 \mathcal O(\max\{n+\lfloor\frac {k+1} 2\rfloor\})，可以通过本题。

注意：当 n=1 时要特判一下，答案显然为 k 而不是长长的式子。

代码

戳我qwq。

参考资料

洛谷日报#401。

特别鸣谢

感谢在求助帖中帮忙的大佬们！！！