二项式反演
__ryp__
·
·
个人记录
设 g(i) 表示选出恰好 i 个元素进行组合的方案数，f(i) 表示选出至少 i 各元素组合的方案数，那么有
f(n) = \sum\limits_{i=0}^n {n\choose i}g(i)
有些时候 f(i) 好计算，而 g(i) 由于恰好的那个限制，不好计算，我们考虑怎么反推。
事实上，有
g(n) = \sum\limits_{i=0}^n {n \choose i}(-1)^{n-i}
这个用组合数的性质是好证的。
于是我们就可以将 f(i) 转化为 g(i)，例题，也是我接触这玩意儿的第一道题是 P10596 集合计数。