「AtCoder Regular Contest 096」E. Everything on It

Problem

Description

给定 n ,求在 \left\{1,2,...,n\right\} 的所有 2^{n} 个子集中选出若干个使其满足每个元素都至少在两个被选中的集合中出现的方案数。

答案对给定质数 p 取模。

Constraints

1\le n\le 3000,10^{8}\le p\le 10^{9}+9

Solution

Analysis

考虑容斥,发现有 i 个元素不合法即出现次数 \le 2 的方案数 f_{i} 不容易直接求。
多加一个限制,令 g_{i,j} 表示将这 i 个不合法元素分配到 j 个集合中的方案数,可得:

g_{i,j}=g_{i-1,j-1}+(j + 1)g_{i-1,j}

h_{i,j} 为在 g_{i,j} 基础上多考虑 n-i 个自由元素的方案数,有:

h_{i,j}=2^{2^{n-i}}\left(2^{n-i}\right)^{j}g_{i,j}

f_{i}=\sum_{j=0}^{i}h_{i,j}

答案即为:

\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}f_{i}

时间复杂度 O(n^{2})

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(3000);

inline int io(){
static int _;
return scanf("%d",&_),_;
}

int inv[maxn+1],
C[maxn+1],
S[maxn+1][maxn+1];

int main(){
const int n=io(),p=io();

const auto inc=[p](auto&x,const auto&y){x+=y;(p<=x)&&(x-=p);};
const auto pls=[p](const auto&x,const auto&y){return x+y<p?x+y:(x+y-p);};

inv[1]=1;
for(int i=2;i!=n;++i)
inv[i]=(i64)inv[p%i]*(p-p/i)%p;

C[0]=C[n]=1;
for(int i=1;i!=n;++i)
C[i]=(i64)C[i-1]*inv[i]%p*(n-i+1)%p;

S[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=(S[i][0]=1);j<=i;++j)
S[i][j]=(S[i-1][j-1]+(i64)S[i-1][j]*(j+1))%p;

i64 ans=0;
for(int i=n,pw=1,pw2=2;~i;--i,inc(pw,pw),pw2=(i64)pw2*pw2%p){
i64 t=0;
for(int j=0,pw3=1;j<=i;++j,pw3=(i64)pw3*pw%p)
t+=(i64)pw3*S[i][j]%p;
(i&1)?(ans-=t%p*pw2%p*C[i]%p):(ans+=t%p*pw2%p*C[i]%p);
}

printf("%d",pls(ans%p,p));

return 0;
}