思路
按照一般逻辑来说这题得自己做了, \(\rm{trick}\) 都见完了
转化题意,
对于 \(m\) 组物品, 每组物品有 \(c_i\) 个, 考虑分配给 \(n\) 个人保证每个人至少有一个物品, 求分配方案的总数
首先简单的是不管每个人至少有一个物品, 直接随机分配, 显然的, 总共的可能性是 \(\displaystyle n^{\sum_{i = 1}^{m} c_i}\)
这个可以容斥那些人没有物品, 但是你发现不能够状压 (即使能够状压, 也不好做, 因为没法求出「恰好」的方案数) , 那怎么办?
肯定要换实现方式了 (绝对不是因为我看到 \(\rm{lhs}\) 使用了二项式反演)
你考虑令 \(f(k)\) 表示「至少」有 \(k\) 个人没有物品, \(g(k)\) 表示「恰好」有 \(k\) 个人没有物品
套路的(还是写一遍)
\[f(k) = \sum_{i = k}^{n} {i \choose k} g(i) \iff g(k) = \sum_{i = k}^{n} (-1)^{i - k} {i \choose k} f(i) \]考虑计算 \(f\)
容易发现
\[f(k) = {n \choose k}\displaystyle (n - k)^{\sum_{i = 1}^{m} c_i} \]结束了
完蛋了跟 \(\rm{TJ}\) 柿子不一样怎么办, 红温了
仔细一想发现上面的柿子 「確有問題」, 显然的会出现一些重复的情况计算, 因为对于单组物品本质不同
所以我们改一下, 用插板法处理
最终的答案为 (常用插板法)
\[f(k) = {n\choose k}\prod_{j=1}^m{c_j+n-k-1\choose n-k-1} \]总结
善于转化问题
常见套路, 「钦定」意义下, 通过「至少」和「恰好」的转化来简化问题, \(f\) 可以用各种方法计算得来
慢慢的理解了这一类问题, 可以做一些简单题了!
相同本质的问题, 一定要考虑清楚组合数学怎么算是对的
标签：JSOI2011,sum,插板,特产,choose,物品,rm From： https://www.cnblogs.com/YzaCsp/p/18644691