外观
组合计数
2026-10-07
题目要求所有人都被分到了特产,不妨从有没有被分到来进行二项式反演。 设 f(k)f(k)f(k) 表示有至少 kkk 个人没被分到特产,也就是 n−kn-kn−k 个人可以分到也可以不分,注意到此时每种特产相互独立,所以:
f(k)=(nk)∏i=1m(ai+n−k−1n−k−1)f(k)=\binom n k \prod_{i=1}^m \binom{a_i+n-k-1}{n-k-1} f(k)=(kn)i=1∏m(n−k−1ai+n−k−1)
直接进行二项式反演,对应的 g(k)g(k)g(k) 表示恰好 kkk 个人没分到特产:
g(k)=∑i=kn(−1)i−k(ik)∏j=1m(aj+n−i−1n−i−1)g(k)=\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \prod_{j=1}^m \binom{a_j+n-i-1}{n-i-1} g(k)=i=k∑n(−1)i−k(ki)j=1∏m(n−i−1aj+n−i−1)
使用 O(n2)O(n^2)O(n2) 计算即可。
版权归属:lyrgo
许可证:署名 4.0 国际 (CC-BY-4.0)