SOSdp 简介 (by zzuzxy)
翻译自：
codeforces sos dp
先学知识：状压dp
SOSdp
全称是
S
u
m
o
v
e
r
S
u
b
s
e
t
s
d
y
n
a
m
i
c
p
r
o
g
r
a
m
m
i
n
g
Sum\ over\ Subsets\ dynamic\ programming
S
u
m
o
v
e
r
S
u
b
s
e
t
s
d
y
n
a
m
i
c
p
r
o
g
r
a
m
m
i
n
g
, 意思就是子集和dp，其实在我看来就是状压dp的一种
从一个例题引出
S
O
S
d
p
SOSdp
S
O
S
d
p
F
[
m
a
s
k
]
=
∑
i
∈
m
a
s
k
A
[
i
]
F[mask] =\sum_{i \in mask}A[i]
F
[
m
a
s
k
]
=
i
∈
m
a
s
k
∑
A
[
i
]
我们说
i
∈
m
a
s
k
i \in mask
i
∈
m
a
s
k
即为
i
&
m
a
s
k
=
i
i \& mask = i
i
&
m
a
s
k
=
i
, 回忆状压
d
p
dp
d
p
，这应该很好理解
然后你发现，咦不太对，这个和
F
W
T
FWT
F
W
T
好像，
i
&
m
a
s
k
=
i
和
i
∣
m
a
s
k
=
m
a
s
k
i\&mask = i 和 i|mask=mask
i
&
m
a
s
k
=
i
和
i
∣
m
a
s
k
=
m
a
s
k
是一回儿事
所以破案了，
F
W
T
=
S
O
S
d
p
FWT = SOS dp
F
W
T
=
S
O
S
d
p
FWT
方法1，
O
(
4
n
)
O(4^n)
O
(
4
n
)
暴力枚举
for(int mask =0;mask < (1<<N); ++i){
for(int i = 0;i < (1<<N); ++i)
if(i&mask == i)
F[mask] += A[i];
}
方法2，
O
(
3
n
)
O(3^n)
O
(
3
n
)
枚举所有子集
for(int mask = 0;mask < (1<<N); ++mask){
F[mask] = A[0];
for(int i = mask; i > 0; i = (i-1)&mask)
F[mask] += A[i];
}
方法3，SOS dp
O
(
n
∗
l
o
g
(
n
)
)
O(n*log(n))
O
(
n
∗
l
o
g
(
n
)
)
d
p
[
m
a
s
k
]
[
i
]
dp[mask][i]
d
p
[
m
a
s
k
]
[
i
]
代表
x
&
m
a
s
k
=
x
,
x
∧
m
a
s
k
<
2
i
+
1
x\&mask = x,x^{\land} mask < 2^{i+1}
x
&
m
a
s
k
=
x
,
x
∧
m
a
s
k
<
2
i
+
1
的
A
[
x
]
A[x]
A
[
x
]
的和, 意思就是
d
p
[
m
a
s
k
]
[
i
]
dp[mask][i]
d
p
[
m
a
s
k
]
[
i
]
是和
m
a
s
k
mask
m
a
s
k
只有前
i
i
i
个位不同的
A
[
x
]
A[x]
A
[
x
]
的和
d
p
[
m
a
s
k
]
[
i
]
=
d
p
[
m
a
s
k
]
[
i
−
1
]
m
a
s
k
&
(
2
i
)
=
0
d
p
[
m
a
s
k
]
[
i
−
1
]
+
d
p
[
m
a
s
k
⊕
(
2
i
)
]
[
i
−
1
]
m
a
s
k
&
(
2
i
)
=
2
i
dp[mask][i] = \begin {matrix} dp[mask][i-1]&mask\&(2^i)=0\\ dp[mask][i-1]+dp[mask\oplus(2^i)][i-1]&mask\&(2^i) = 2^i \end{matrix}
d
p
[
m
a
s
k
]
[
i
]
=
d
p
[
m
a
s
k
]
[
i
−
1
]
d
p
[
m
a
s
k
]
[
i
−
1
]
+
d
p
[
m
a
s
k
⊕
(
2
i
)
]
[
i
−
1
]
m
a
s
k
&
(
2
i
)
=
0
m
a
s
k
&
(
2
i
)
=
2
i
如下图
//iterative version
for(int mask = 0; mask < (1<<N); ++mask){
dp[mask][-1] = A[mask]; //handle base case separately (leaf states)
for(int i = 0;i < N; ++i){
if(mask & (1<<i))
dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
else
dp[mask][i] = dp[mask][i-1];
}
F[mask] = dp[mask][N-1];
}
//memory optimized, super easy to code.
for(int i = 0; i<(1<<N); ++i)
F[i] = A[i];
for(int i = 0;i < N; ++i) for(int mask = 0; mask < (1<<N); ++mask){
if(mask & (1<<i))
F[mask] += F[mask^(1<<i)];
}
扩展及应用
-
CF1208F
题意
：求
ma
x
(
a
i
∣
(
a
j
&
a
k
)
)
,
1
≤
i
<
j
<
k
≤
n
max(a_i |(a_j\&a_k)),1\leq i<j<k\leq n
m
a
x
(
a
i
∣
(
a
j
&
a
k
)
)
,
1
≤
i
<
j
<
k
≤
n
分析
: 从后往前依次将每一个数加入
SO
S
d
p
SOSdp
S
O
S
d
p
中，记忆化一下
参考代码
:
code
-
SPECIAL PAIRS
题意
： 求
ai
&
a
j
=
0
a_i\&a_j=0
a
i
&
a
j
=
0
的
(i
,
j
)
(i,j)
(
i
,
j
)
的个数
分析
：sos dp 即可
参考代码：
code1-FWT
code2-sosdp
-
E. Compatible Numbers
题意
： 给定
a1
,
.
.
a
n
a_1,..a_n
a
1
,
.
.
a
n
求对于每一个
ai
a_i
a
i
是否存在
aj
a_j
a
j
满足
ai
&
a
j
=
0
a_i\&a_j=0
a
i
&
a
j
=
0
分析
：同上一题一样，只需要记录一下转移从何处而来即可 -
E – Vowels
题意
：字符集大小为24，有n个单词，每个单词有三个字母，如果其中有一个元音，我们就称这个单词是合法的，元音的集合有
224
2^{24}
2
2
4
种可能，求这
224
2^{24}
2
2
4
种元音集合的正确单词数的平方的异或和。
分析
：现在的问题变成了
ai
&
m
a
s
k
!
=
0
a_i\&mask != 0
a
i
&
m
a
s
k
!
=
0
,我们注意到字母的个数很小，那么我们就可以使用容斥定理，求出一个字母的，两个字母，三个字母的贡献，然后进行
SO
S
d
p
SOSdp
S
O
S
d
p
即可
参考代码
:
code
-
Covering Sets CodeChef – COVERING
题意
: 给定集合
A,
B
,
C
A,B,C
A
,
B
,
C
,定义运算
A(
i
)
,
B
(
i
)
,
C
(
i
)
A(i),B(i),C(i)
A
(
i
)
,
B
(
i
)
,
C
(
i
)
，返回集合的第i个值(从0开始), 定义一个三元组
(A
(
i
)
,
B
(
j
)
,
C
(
k
)
)
(\textbf A(i),\textbf B(j),\textbf C(k))
(
A
(
i
)
,
B
(
j
)
,
C
(
k
)
)
的并集为
i∣
j
∣
k
i|j|k
i
∣
j
∣
k
,如果
l&
(
i
∣
j
∣
k
)
=
l
l \&(i|j|k) = l
l
&
(
i
∣
j
∣
k
)
=
l
,那么我们就称
(A
(
i
)
,
B
(
j
)
,
C
(
k
)
)
(\textbf A(i),\textbf B(j),\textbf C(k))
(
A
(
i
)
,
B
(
j
)
,
C
(
k
)
)
覆盖
ll
l
，
R(
l
)
R(l)
R
(
l
)
定义所有的覆盖 l的三元组的乘积的和即
R(
l
)
=
∑
l
&
(
i
∣
j
∣
k
)
=
l
A
(
i
)
∗
B
(
j
)
∗
C
(
k
)
R(l) = \sum_{l\&(i|j|k)=l} A(i)*B(j)*C(k)
R
(
l
)
=
l
&
(
i
∣
j
∣
k
)
=
l
∑
A
(
i
)
∗
B
(
j
)
∗
C
(
k
)
求
R(
0
)
+
R
(
1
)
+
R
(
2
)
+
.
.
.
R
(
2
N
−
1
)
R(0)+R(1)+R(2)+…R(2^N-1)
R
(
0
)
+
R
(
1
)
+
R
(
2
)
+
.
.
.
R
(
2
N
−
1
)
分析
：直接枚举
ll
l
求满足的集合是不行的，我们可以统计每一个三元组
(A
(
i
)
,
B
(
j
)
,
C
(
k
)
)
(\textbf A(i),\textbf B(j),\textbf C(k))
(
A
(
i
)
,
B
(
j
)
,
C
(
k
)
)
的贡献,我们发现它能够对
t=
2
d
(
i
∣
j
∣
k
)
t = 2^{d (i|j|k)}
t
=
2
d
(
i
∣
j
∣
k
)
个
ll
l
有贡献 ，所以我们统计所有的三元组，这样的复杂度过大，但是如果
i∣
j
∣
k
i|j|k
i
∣
j
∣
k
相等的集合统一算贡献就可以了，对
A，
B
，
C
A，B，C
A
，
B
，
C
都计算一次
SO
S
d
p
SOSdp
S
O
S
d
p
, 然后我们就计算出了相乘，但是这样会有重复，我们需要减去
i∣
j
∣
k
i|j|k
i
∣
j
∣
k
的真子集，把
SO
S
d
p
SOSdp
S
O
S
d
p
倒着做一次即可
参考代码
：
code
-
D. Jzzhu and Numbers
给定
a1
,
.
.
a
n
a_1,..a_n
a
1
,
.
.
a
n
求有多少集合按位与的值为0
参考代码
：
code1
-
COCI 2011/2012 Problem KOSARE
给定
a1
,
.
.
.
n
a_1,…_n
a
1
,
.
.
.
n
求有多少个集合按位或为全集
以上两题其实可以看做是一个题，先做一遍
SO
S
d
p
SOSdp
S
O
S
d
p
求出
F[
m
a
s
k
]
F[mask]
F
[
m
a
s
k
]
，然后容斥
参考代码
：
code2
-
hackrank subsets
题意
：
操作1：在集合中插入一个元素
操作2：在集合中删除一个元素
操作3：查询集合中有多少个元素满足
a&
s
=
a
a\&s =a
a
&
s
=
a
分析
:
我们用
bi
t
(
a
)
bit(a)
b
i
t
(
a
)
表示
aa
a
的二进制表示1的数量
方法1：修改枚举前8位，查询枚举后八位，子集枚举复杂度
O(
Q
∗
8
∗
2
8
)
O(Q*8*2^8)
O
(
Q
∗
8
∗
2
8
)
dp
[
i
]
[
j
]
dp[i][j]
d
p
[
i
]
[
j
]
代表
lo
w
8
&
i
=
l
o
w
8
,
h
i
g
h
8
=
j
low_8 \&i=low_8,high_8 = j
l
o
w
8
&
i
=
l
o
w
8
,
h
i
g
h
8
=
j
的a个数
修改的时候枚举包含前八位的集合
查询的时候，枚举后八位的子集，前8位的子集就是
dp
[
l
o
w
8
]
dp[low_8]
d
p
[
l
o
w
8
]
方法2：维护3个数组
F,
D
,
E
F,D,E
F
,
D
,
E
F: 维护的是
aa
a
中
bi
t
(
a
)
>
8
)
bit(a)>8)
b
i
t
(
a
)
>
8
)
，
F[
i
]
F[i]
F
[
i
]
就是通常的
F[
m
a
s
k
]
F[mask]
F
[
m
a
s
k
]
,即
ma
s
k
&
a
=
a
mask\&a =a
m
a
s
k
&
a
=
a
D:维护的是
aa
a
中
bi
t
(
a
)
≤
8
bit(a)\leq 8
b
i
t
(
a
)
≤
8
,
D[
i
]
D[i]
D
[
i
]
是
a=
i
a=i
a
=
i
的a的数量
E:维护的是
aa
a
中
bi
t
(
a
)
≤
8
bit(a)\leq 8
b
i
t
(
a
)
≤
8
,
E[
m
a
s
k
]
E[mask]
E
[
m
a
s
k
]
是
ma
s
k
&
a
=
m
a
s
k
mask\& a=mask
m
a
s
k
&
a
=
m
a
s
k
的数量
修改操作-
bi
t
(
a
)
≤
8
bit(a) \leq 8
b
i
t
(
a
)
≤
8
,修改
D,
E
D,E
D
,
E
-
bi
t
(
a
)
>
8
bit(a) > 8
b
i
t
(
a
)
>
8
,修改F，修改F就直接暴力修改，枚举所有包含
a&
m
a
s
k
=
a
a\&mask = a
a
&
m
a
s
k
=
a
的集合
查询操作 -
bi
t
(
s
)
≤
8
bit(s) \leq 8
b
i
t
(
s
)
≤
8
, 查询
DD
D
即可，枚举
aa
a
的所有子集 -
bi
t
(
s
)
>
8
bit(s) > 8
b
i
t
(
s
)
>
8
,
F[
s
]
F[s]
F
[
s
]
为
bi
t
(
a
)
>
8
bit(a) > 8
b
i
t
(
a
)
>
8
的贡献，考虑怎么求
bi
t
(
a
)
≤
8
bit(a) \leq 8
b
i
t
(
a
)
≤
8
的贡献，我们对
ss
s
取反得到
ss
ss
s
s
,求
a&
s
s
!
=
0
a\&ss!=0
a
&
s
s
!
=
0
的个数，这就变成了第4题
参考代码
code 1
code2
-
-
Jersey Number
题意
:给定一个字符串，求有多少对区间有至少一个相同的字符
分析
：（icpc上这道题不能提交，数据是错的）先处理出来所有的区间的值，然后进行
SO
S
d
p
SOSdp
S
O
S
d
p
即可
参考代码
：
code
-
Beautiful Sandwich
题意
：给定一个字符串，字符集不超过18个，定义一个字符串的value 为 连续相同字符个数的平方，求每次删除几种字符后字符串的价值。
分析
：仔细想想其实和上一题有相似之处，平方我们可以拆开，
A∗
A
=
(
1
+
.
.
.
1
)
A
个
1
∗
(
1
+
.
.
.
1
)
A
个
1
A*A = {(1+…1)}_{A个1}*{(1+…1)}_{A个1}
A
∗
A
=
(
1
+
.
.
.
1
)
A
个
1
∗
(
1
+
.
.
.
1
)
A
个
1
,1代表一个字符出现一次，例如
ab
a
c
a
a
abacaa
a
b
a
c
a
a
，我们考虑第一个a的贡献，从位置1开始，每次加入一个新的
aa
a
，如果删除
bb
b
，那么增加的值是
1(
第
一
个
a
)
∗
1
(
第
二
个
a
)
∗
2
1(第一个a)*1(第二个a)*2
1
(
第
一
个
a
)
∗
1
(
第
二
个
a
)
∗
2
,如果删除
bc
bc
b
c
,那么贡献就又增加了
1∗
2
(
第
三
个
，
第
四
个
a
)
∗
2
1*2(第三个，第四个a)*2
1
∗
2
(
第
三
个
，
第
四
个
a
)
∗
2
,这样就把贡献拆开，利用
SO
S
d
p
SOSdp
S
O
S
d
p
来做
参考代码
：
code,注意爆int
-
K. Pepsi Cola
题意
： 求
2N
2^N
2
N
子集合所有元素或的三次方
分析
：需要求出来每个值有多少个集合，采用
SO
S
d
p
SOSdp
S
O
S
d
p
,需要搞懂第5题 -
Uchiha Brothers and Two Products
题意
：物品有两个属性，价值
pi
p_i
p
i
和营养价值
ai
a_i
a
i
，定义一个集合的营养价值为
&a
i
(
i
∈
S
)
\&a_i(i\in S)
&
a
i
(
i
∈
S
)
,定义一个集合的价值为
∏i
∈
S
p
i
\prod_{i\in S} p_i
∏
i
∈
S
p
i
，给定营养价值
ss
s
，取所有营养价值相同为s的集合的价值的和.
分析
：会发现营养价值这个条件就是
SO
S
d
p
SOSdp
S
O
S
d
p
的内容，怎么将所有营养价值的和变成乘积，最后发现这个其实也是dp,比方说加入一个价值为b的
dp
[
i
]
=
d
p
[
i
]
+
d
p
[
i
]
∗
b
+
b
dp[i] = dp[i]+dp[i]*b+b
d
p
[
i
]
=
d
p
[
i
]
+
d
p
[
i
]
∗
b
+
b
.将原本sosdp的内容修改即可，然后我们求出来
F[
m
a
s
k
]
F[mask]
F
[
m
a
s
k
]
，依然要做一次反
SO
S
d
p
SOSdp
S
O
S
d
p
参考代码
：
code
-
Strange Functions
题意
：给定
A[
i
]
A[i]
A
[
i
]
,已知
F[
i
]
=
A
[
i
]
2
+
∑
(
i
&
j
)
=
j
a
n
d
j
<
i
G
[
j
]
)
2
G
[
i
]
=
∑
(
i
&
j
)
=
j
a
n
d
j
≤
i
(
F
[
j
]
)
2
\quad \quad F[i] = {A[i]}^2 +\sum_{(i\&j) = j\ and\ j < i} G[j])^2 \\ \quad\\ G[i] = ∑_{ (i\&j) = j\ and\ j ≤ i} {(F[j])}^2
F
[
i
]
=
A
[
i
]
2
+
(
i
&
j
)
=
j
a
n
d
j
<
i
∑
G
[
j
]
)
2
G
[
i
]
=
(
i
&
j
)
=
j
a
n
d
j
≤
i
∑
(
F
[
j
]
)
2
分析
: 老老实实按照
dp
[
m
a
s
k
]
[
i
]
dp[mask][i]
d
p
[
m
a
s
k
]
[
i
]
来维护
∑G
[
i
]
\sum{G[i]}
∑
G
[
i
]
和
∑F
[
i
]
2
\sum{F[i]}^2
∑
F
[
i
]
2
参考代码
:
code
-
D. Varying Kibibits
题意
：题意有些复杂，建议自己理解
分析
：怎么维护平方呢？不知道有没有做过线段树维护区间和平方那个题，就是维护一次项和二次项，怎么维护集合的平方呢？考虑再维护集合的个数即可，最后做一遍反 SOSdp即可
参考代码
:
code