标签：等比数列 计数 交集 sum 套路 BZOJ2839 choose 集合

思路

直接计算不好计算, 套路的, 考虑「至少」「至多」来转化

容易发现你「钦定」\(k\) 个元素在交集之中, 也就是说交集大小「至少」为 \(k\) , 怎么处理这个的方案数, 其实比较容易可以发现, 这个的方案数为

\[f(k) = {n \choose k} \sum_{i = 0}^{n - k} 2^i \]

不够优, 考虑转化, 这是一个等比数列, 等比数列求和带进去发现

\[f(k) = {n \choose k} (2^{2^{n - k}} - 1) \]

带进套路里, 令 \(g(k)\) 表示「恰好」选择了 \(k\) 个元素在交集之中

你容易发现

\[f(k) = \sum_{i = k}^{n} {n \choose i} g(i) \iff g(k) = \sum_{i = k}^{n} (-1)^{i - k} {n \choose i} f(i) \]

套进去算即可

总结

常见套路, 板子题

注意很多问题要带一个组合数表示选择那些

标签：等比数列,计数,交集,sum,套路,BZOJ2839,choose,集合
From： https://www.cnblogs.com/YzaCsp/p/18640233