CF755G

时间：2020-06-14 09:50:42 阅读：32 评论：0 收藏：0 [点我收藏+]

\(n\)个球，\(m\)个盒子，每个盒子要么放一个球，要么放相邻的两个球，不要求将球全部放完，求\(i\in[1,m]\)，总共有\(i\)个盒子的方案数

枚举相邻两个球的盒子数

\[ans_i=\sum\limits{i\choose j}{n-j\choose i} \]

考虑其组合意义：\(n\)个球，在前\(i\)个球选若干个，除此之外其余的球中选\(i\)个
考虑容斥计算，枚举前\(i\)个球中选择的球与之后的球中重复选择了\(j\)个，枚举前\(i\)个球的状态

\[ans_i=\sum\limits(-1)^j{i\choose j}2^{i-j}{n-j\choose i-j} \]

原文：https://www.cnblogs.com/Grice/p/13121763.html

踩

(0)

评论一句话评论（0）

分享档案

更多>