问题描述：
小S有 个盒子，每个盒子里都装着若干个玩具。玩具一共有 种不同的类型。 现在，小S想要知道有多少种不同的挑选盒子的方式，使得每种种类的玩具都至少在这些盒子里出现了一次。 请输出答案对
1
e
9
+
7
1e9+7
1e9+7取模的值。
50
%
N
≤
100
,
M
≤
15
50\%\ N ≤ 100,M ≤ 15
50% N≤100,M≤15
70
%
N
≤
1
0
6
,
M
≤
15
70\%\ N ≤ 10^6,M ≤ 15
70% N≤106,M≤15
100
%
N
≤
1
0
6
,
M
≤
20
100\%\ N ≤ 10^6,M ≤ 20
100% N≤106,M≤20
Solution
首先我们看到这个数据范围，就有了一种状压的冲动 不妨把每一个盒子都看成一个
m
m
m位二进制数，其中有哪种类型的球哪一位便是1，其余都是0. 那么问题便转化成了：给定n个二进制数，求其中几个二进制数
o
r
or
or起来m位全部是1的方案数。
50分
按照如上所说的方法把每一个盒子都处理成二进制数后再进行递推即可
Code
#include<bits/stdc++.h>
using namespace std
;
const int p
= 1e9+7;
int lowbit(int x
){return x
&-x
;}
int n
,m
,ans
=0;
int num
[1<<20];
int mp
[1<<20];
int f
[1<<20];
vector
< int > to
[1001000];
int main(){
freopen("toy.in","r",stdin);
freopen("toy.out","w",stdout);
scanf("%d %d",&n
,&m
);
for (int i
=1;i
<=n
;i
++){
int le
,x
;
scanf("%d",&le
);
for (int j
=1;j
<=le
;j
++)
scanf("%d",&x
),to
[i
].push_back(x
);
}
for (int i
=1;i
<=n
;i
++)
for (int j
=0;j
<to
[i
].size();j
++)
num
[i
] |= (1<<(to
[i
][j
]-1));
f
[0] = 1;
for (int i
=1;i
<=n
;i
++)
for (int j
=(1<<m
)-1;j
>=0;j
--)
f
[j
|num
[i
]]+=f
[j
],f
[j
|num
[i
]]%=p
;
printf("%d",f
[(1<<m
)-1]%p
);
return 0;
}
那么此时便来想正解。 对于这一类状压类问题，其实大多数都可以用
容
斥
原
理
容斥原理
容斥原理做的
我们尝试逆着推问题：是否可以用一个包含一个完整集合以及他子集的方案数减去他子集的方案数从而解得问题？
我们用
g
[
i
]
g[i]
g[i]表示状态为i的盒子的个数而用
g
[
i
]
g[i]
g[i]可以推得包含状态为i以及i的子集的盒子的总个数
g
[
i
]
(
仍
然
用
g
[
i
]
b
表
示
)
g[i](仍然用g[i]b表示)
g[i](仍然用g[i]b表示)而对于每个
g
[
i
]
g[i]
g[i]，选他以及他的子集的方案数一共是
2
g
[
i
]
2^{g[i]}
2g[i]种（由于是等价的，所以不管选几个选那些都行，可由
C
g
[
i
]
0
+
C
g
[
i
]
1
+
…
…
+
C
g
[
i
]
g
[
i
]
C_{g[i]}^0+C_{g[i]}^1+……+C_{g[i]}^{g[i]}
Cg[i]0+Cg[i]1+……+Cg[i]g[i]推得）
利用容斥原理公式可以得到答案为：
∑
s
2
g
[
s
]
(
−
1
)
s
−
∣
s
∣
(
∣
s
∣
表
示
他
的
子
集
)
\sum_s2^{g[s]}(-1)^{s-|s|}(|s|表示他的子集)
s∑2g[s](−1)s−∣s∣(∣s∣表示他的子集)
递推减去他的子集的方案即可解得最终状态为
(
1
<
<
m
)
−
1
(1<<m)-1
(1<<m)−1的方案
Code
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int P
= 1e9+7;
int n
,m
;
int g
[(1<<20)+100];
int f
[(1<<20)+100];
int p
[(1<<20)+10];
signed main(){
freopen("toy.in","r",stdin);
freopen("toy.out","w",stdout);
scanf("%lld %lld",&n
,&m
);
for (int i
=1;i
<=n
;i
++){
int len
,x
,
num
= 0;
scanf("%lld",&len
);
for (int j
=1;j
<=len
;j
++)
scanf("%lld",&x
),num
|= 1<<(x
-1);
g
[num
]++;
}
p
[0] = 1;
for (int i
=1;i
<=1<<20;i
++)
p
[i
] = (p
[i
-1]<<1)%P
;
for (int i
=0;i
<m
;i
++)
for (int j
=1;j
<=(1<<m
)-1;j
++)
if (j
&(1<<i
))
g
[j
] = (g
[j
]%P
+g
[j
^(1<<i
)]%P
)%P
;
for (int i
=0;i
<(1<<m
);i
++)
f
[i
] = (p
[g
[i
]])%P
;
for (int i
=0;i
<m
;i
++)
for (int j
=(1<<m
)-1;j
>0;j
--)
if (j
&(1<<i
))
f
[j
] = (f
[j
]-f
[j
^(1<<i
)]+P
)%P
;
printf("%lld",f
[(1<<m
)-1]%P
);
return 0;
}
