原题目链接。
在 洛谷 上看此题解。
声明：本文章需经作者允许方可转载。
神奇的题目。
结论
设子集元素按非降序排列为
b
1
≤
b
2
≤
⋯
≤
b
k
b_1 \\leq b_2 \\leq \\dots \\leq b_k
b1≤b2≤⋯≤bk，定义前缀和
s
0
=
0
s_0=0
s0=0，$s_i=b_1+b_2+\\dots+b_i $（即 $s_k=x $）。 该子集是“好子集”的充要条件为：对所有
1
≤
i
≤
k
1 \\leq i\\leq k
1≤i≤k，满足
b
i
≤
s
i
−
1
+
1
b_i\\leq s_{i-1}+1
bi≤si−1+1。
下面提供两种证明：
反证法 若存在某
i
i
i 使得
b
i
>
s
i
−
1
+
1
b_i>s_{i-1}+1
bi>si−1+1，则前
i
−
1
i-1
i−1 个元素最大可表示
s
i
−
1
s_{i-1}
si−1，而
b
i
>
s
i
−
1
+
1
b_i>s_{i-1}+1
bi>si−1+1 意味着
s
i
−
1
+
1
s_{i-1}+1
si−1+1 无法通过“前
i
−
1
i-1
i−1 个元素的组合”或“前
i
−
1
i-1
i−1 个元素的组合 +
b
i
b_i
bi”得到（后者最小为
b
i
>
s
i
−
1
+
1
b_i>s_{i-1}+1
bi>si−1+1），与“好子集”定义矛盾。
数学归纳法
-
k
=
1
k=1
k=1
此时
b
1
≤
s
0
+
1
=
1
b_1\\leq s_0+1=1
b1≤s0+1=1，故
b
1
=
1
b_1=1
b1=1，子集总糖果数
x
=
1
x=1
x=1，显然可表示
y
=
1
y=1
y=1，满足“好子集”定义。
-
假设
k
=
i
−
1
k=i-1
k=i−1 成立，证
k
=
i
k=i
k=i 成立
假设前
i
−
1
i-1
i−1 个元素可表示
[
1
,
s
i
−
1
]
[1,s_{i-1}]
[1,si−1] 中所有数。加入
b
i
b_i
bi 后，新前缀和
s
i
=
s
i
−
1
+
b
i
s_i=s_{i-1}+b_i
si=si−1+bi。 对任意
y
∈
[
1
,
s
i
]
y\\in[1,s_i]
y∈[1,si]：
- 若
y
∈
[
1
,
s
i
−
1
]
y\\in[1,s_{i-1}]
y∈[1,si−1]：由归纳假设，可通过前i
−
1
i-1
i−1 个元素表示； - 若
y
∈
[
s
i
−
1
+
1
,
s
i
]
y\\in[s_{i-1}+1,s_i]
y∈[si−1+1,si]：则y
−
b
i
∈
[
s
i
−
1
+
1
−
b
i
,
s
i
−
1
]
y – b_i \\in[s_{i-1}+1-b_i,s_{i-1}]
y−bi∈[si−1+1−bi,si−1]。由充要条件b
i
≤
s
i
−
1
+
1
b_i\\leq s_{i-1}+1
bi≤si−1+1，得y
−
b
i
≥
0
y – b_i \\geq 0
y−bi≥0。若y
−
b
i
=
0
y-b_i=0
y−bi=0，则直接取b
i
b_i
bi 即可；若y
−
b
i
>
0
y-b_i>0
y−bi>0，则y
−
b
i
∈
[
1
,
s
i
−
1
]
y-b_i\\in[1,s_{i-1}]
y−bi∈[1,si−1]，由归纳假设可表示，故y
=
(
y
−
b
i
)
+
b
i
y=(y-b_i)+b_i
y=(y−bi)+bi 可表示。
- 若
因此前
i
i
i 个元素可表示
[
1
,
s
i
]
[1,s_i]
[1,si] 中所有数。
思路
然后很明显使用动态规划。
首先将数组
a
a
a 按非降序排列，因为处理元素时始终从最小未处理元素开始，这样就可以利用前缀和条件
b
i
≤
s
i
−
1
+
1
b_i\\leq s_{i-1}+1
bi≤si−1+1（若当前元素已满足对当前前缀和的条件，那么后续更大元素无需额外判断）。
然后就是状态定义：设
d
p
i
dp_i
dpi 表示前缀和为
i
i
i 的好子集数量。
注意这里有一个重要的优化点，由于
a
i
≤
5000
a_i \\leq 5000
ai≤5000，当
s
≥
5000
s\\geq5000
s≥5000 时，任意
a
i
≤
5000
≤
s
+
1
a_i\\leq5000\\leq s+1
ai≤5000≤s+1（因
s
≥
5000
⟹
s
+
1
≥
5001
>
a
i
s\\geq5000\\implies s+1\\geq 5001>a_i
s≥5000⟹s+1≥5001>ai），故所有
s
≥
5000
s\\geq5000
s≥5000 的状态可合并为
d
p
5000
dp_{5000}
dp5000，无需记录具体值。
转移方程，对每个元素
a
i
a_i
ai，倒序遍历前缀和
s
s
s，避免重复计算，类似 01 背包：若
s
≥
a
i
−
1
s\\geq a_i-1
s≥ai−1（即
a
i
≤
s
+
1
a_i\\leq s+1
ai≤s+1，满足充要条件），则可将
a
i
a_i
ai 加入前缀和为
s
s
s 的好子集，新前缀和为
min
(
s
+
a
i
,
5000
)
\\min(s+a_i,5000)
min(s+ai,5000)，转移式为：
d
p
min
(
s
+
a
i
,
5000
)
=
(
d
p
min
(
s
+
a
i
,
5000
)
+
d
p
s
)
m
o
d
(
10
9
+
7
)
dp_{\\min(s+a_i,5000)}=(dp_{\\min(s+a_i,5000)}+ dp_s)\\bmod (10^9+7)
dpmin(s+ai,5000)=(dpmin(s+ai,5000)+dps)mod(109+7)
注意边界
d
p
0
=
1
dp_0=1
dp0=1 表示空集。
最终答案就是所有非空好子集的数量，即
∑
s
=
1
5000
d
p
s
m
o
d
(
10
9
+
7
)
\\sum_{s=1}^{5000} dp_s \\bmod (10^9+7)
∑s=15000dpsmod(109+7)（空集肯定是不计入，故从
s
=
1
s=1
s=1 开始累加）。
代码
试过了，填表法可能有问题，所以还是用刷表法吧。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,a[5001],dp[5005],ans;
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=5000;j>=a[i]–1;j—){
dp[min(5000ll,a[i]+j)]=(dp[min(5000ll,a[i]+j)]+dp[j])%mod;
}
}
for(int i=1;i<=5000;i++)ans=(ans+dp[i])%mod;
cout<<ans;
}
