考慮容斥，最后的答案為∑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的情況.

丑陋的代碼