bzoj2839 关于组合数的若干yy

考虑容斥，最后的答案为∑ni=k(−1)i−k∗Cin∗Cki∗(22n−i−1)$/sum_{i=k}^{n}(-1)^{i-k}*C_{n}^{i}*C_{i}^{k}*(2^{2^{n-i}}-1)$ 实际上-1和最后一部分并不需要解释，然后我们看看如何证明这个的正确性。

辣鸡的证明

关于普通的容斥原理，我们可以用二项式定理yy 当我们发现对于每一个交集大小为n的选法，他最后被统计的次数是这个. ∑ni=k(−1)i−kCin∗Cki$/sum_{i=k}^{n} (-1)^{i-k}C_{n}^{i}*C_{i}^{k}$由于我菜，就上uoj群问了一发，钊神说这似乎是证明二项式反演的啥啥玩意儿orz. 我们根据组合数的公式，有 Cin∗Cki=Ckn∗Ci−kn−k$C_{n}^{i}*C_{i}^{k}=C_{n}^{k}*C_{n-k}^{i-k}$

那么 ∑ni=k(−1)i−kCin∗Cki=0  (k<n)$/sum_{i=k}^{n} (-1)^{i-k}C_{n}^{i}*C_{i}^{k}=0 / / (k < n)$ =∑ni=k(−1)i−kCi−kn−k=0  (k<n)$/sum_{i=k}^{n} (-1)^{i-k}C_{n-k}^{i-k}=0 / / (k < n)$ =Ckn∑ni=k(−1)i−k∗Ci−kn−k=0  (k<n)$C_{n}^{k}/sum_{i=k}^{n} (-1)^{i-k}*C_{n-k}^{i-k}=0 / / (k < n)$ =Ckn(1−1)n−k$C_{n}^{k}(1-1)^{n-k}$ 考虑这个式子，当n>k的时候，他=0，当n=k时，他=1.这就说明我们最后只算了交集为k的情况.

丑陋的代码