求有多少个子集族，满足：
1、其中任意一个子集都是\([n]\)的子集（包括\(\phi\)）；
2、任意两个子集互不相同；
3、\(1,2,...,n\)都在其中至少出现了\(2\)次。
答案对\(M\)取模。
\(2\leqslant N\leqslant 3000\)，\(10^8\leqslant M\leqslant 10^9+9\)，\(M\)是质数。
（开个随笔记录思路以及细节的）
由于至少出现2次，而且\(N\)的范围很乐观，我们采用容斥（一般用于不好直接求解答案的大部分用容斥的思想）
我们以“出现次数小于2次”来进行容斥，先可以大体写出来这个式子
现在看\(f(i)\)。选出来了\(i\)个数要满足条件，剩余的\(N-i\)个数随便，这\(N-i\)个数构成的集合有\(2^{N-i}\)种，那么可以有\(2^{2^{N-i}}\)种选择方案。回头再来考虑这\(i\)个数怎么选。显然这\(i\)个数要么出现在某一集合中且只出现一次，要么没有出现。这里假定\(i\)个数被分到了\(j+1\)个集合中（+1是单独给没出现的数划的集合），再放入一个标记数字0表示这个数字所在集合为没出现数的集合。那么就是第二类斯特林数\({i+1\brace j+1}\)，然后包含这些数的集合中又可以随便塞入其他\(N-i\)数中的任意组合，故每一个集合会带来\(2^{N-i}\)的贡献，总共就是\(2^{j(N-i)}\)。故
综上
(你似乎来到了一片荒漠)
原文：https://www.cnblogs.com/ac-evil/p/12878297.html