- 有一个集合({1,2,..,n})，问有多少种方式选出它的若干个不同的子集，满足每种元素至少出现两次。
- (nle3 imes10^3)
广义容斥
这种问题显然一眼想到容斥，设(f(i))表示有至少(i)种元素出现次数小于两次的方案数，根据广义容斥的式子就能得到：
[ans=sum_{i=0}^n(-1)^i imes C_n^i imes f(i)
]
所以问题就转化成如何求(f(i))。
第二类斯特林数
首先，有一个需要注意的问题，就是我们是让(i)种元素出现次数小于两次，因此它有可能出现，有可能不出现。
对此，我们可以强行加入一个(0)号元素，让和(0)号元素在一起的那些元素表示不选，那么两种情况就可以一并讨论了。
所以，我们可以直接枚举这(i)种元素总共被选中在(j)个集合中，加上(0)及其所在的不选集合，就是要把(i+1)个元素分到(j+1)个集合中，方案数为第二类斯特林数(S_2(i+1,j+1))。
由于这(i)种仅出现一次的元素的存在，这(j)个集合必然两两不同，且和其余没有这(i)种元素的集合也必然存在差异，因此它们可以任填，方案数为((2^{n-i})^j)。
除了这(j)个集合外，仅由剩余(n-i)个元素组成的子集共有(2^{n-i})个，那么就有(2^{2^{n-i}})种剩余子集的选法。
把这些东西全部合起来得到一个总式子：
[f(i)=2^{2^{n-i}} imes sum_{j=1}^iS_2(i+1,j+1) imes(2^{n-i})^j
]
直接预处理第二类斯特林数计算就完了。
代码：(O(n^2))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 3000
#define C(x,y) (1LL*Fac[x]*IFac[y]%X*IFac[(x)-(y)]%X)
using namespace std;
int n,X,Fac[N+5],IFac[N+5],S2[N+5][N+5];
I int QP(RI x,RI y,CI p=X) {RI t=1;W(y) y&1&&(t=1LL*t*x%p),x=1LL*x*x%p,y>>=1;return t;}
int main()
{
RI i,j,t,s=0;for(scanf("%d%d",&n,&X),Fac[0]=i=1;i<=n;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[i=n]=QP(Fac[n],X-2);i;--i) IFac[i-1]=1LL*IFac[i]*i%X;//预处理阶乘逆元
for(S2[0][0]=i=1;i<=n+1;++i) for(j=1;j<=i;++j) S2[i][j]=(1LL*j*S2[i-1][j]+S2[i-1][j-1])%X;//预处理第二类斯特林数
RI p,pw;for(i=0;i<=n;s=((i&1?X-1LL:1LL)*C(n,i)%X*QP(2,QP(2,n-i,X-1))%X*t+s)%X,++i)//广义容斥
for(p=QP(2,n-i),pw=1,t=j=0;j<=i;pw=1LL*pw*p%X,++j) t=(1LL*S2[i+1][j+1]*pw+t)%X;//根据式子计算
return printf("%d
",s),0;
}