ABC156:E-简单组合数学

例如： n = 3 , k = 2.

状态有:(0,0,3),(0,3,0),(3,0,0),(0,1,2),(0,2,1),(1,2,0),(2,1,0),(1,1,1),(1,0,2),(2,0,1).

$当 k\geq n时$ ,任何局面可以达成，就是求不定方程非负整数解的个数.我们可以用一一映射+插空法。答案为： $C(2*n-1,n-1)$

$当 k< n时$ .等价于： $x_1+...+x_n=n \ \ 且 \ \max\{x_i\} \leq \min\{n,1+k\}$

当时我推到这里就卡住了。想用dp做，但是只能想出 $O(n^2)$ 的.

因为我这里漏掉了一个很重要的条件: 未知数的个数 = 所求的数.

那么就意味着，当存在着一个数 >= k 时，那么必将至少有 k - 1 个空格产生.

所以上述条件可以转换为:局面中存在有 $[0,k]$ 个空房间。

那么我们可以用总的减去不合法的，当然也可以直接算。

空房间的组合情况为： $C(n,i)$

剩下来的房间最少都有1个人，那么可以直接插空法: $C(n-1,n-i-1)$

总答案为： $\sum_{i=0}^{k}C(n,i)*C(n-1,n-i-1)$

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。