P1566 加等式 【洛谷算法习题】

P1566 加等式

网页链接

P1566 加等式

题目描述

对于一个整数集合，我们定义“加等式”如下：集合中的某一个元素可以表示成集合内其他元素之和。如集合1 , 2 , 3 {1,2,3}1,2,3中就有一个加等式：3 = 1 + 2 3=1+23=1+2。而且3 = 1 + 2 3=1+23=1+2和3 = 2 + 1 3=2+13=2+1是相同的加等式，也是这个集合唯一的加等式。给定一个整数集合，编程找出其加等式的个数。

输入格式

第一行为t tt，表示测试数据组数。

接下来t tt行，每行表示一组测试数据。其中第一个数m mm，表示集合元素的个数，接下来m mm个不同的整数x i x_ixi​，表示集合元素。

输出格式

对于每个输入数据，输出一个整数，表示其中加等式的个数。

输入输出样例 #1

输入 #1

3 3 1 2 3 3 1 2 5 6 1 2 3 5 4 6

输出 #1

1 0 7

说明/提示

1 ≤ t ≤ 10 1\le t\le 101≤t≤10，1 ≤ m ≤ 30 1\le m \le 301≤m≤30，1 ≤ x ≤ 1000 1\le x\le 10001≤x≤1000。

解题思路

本题要求统计一个集合中“加等式”的数量，即存在一个元素等于集合中其他元素之和。由于数据规模较小（m ≤ 30 m\le 30m≤30，元素值≤ 1000 \le 1000≤1000），可以采用子集和 DP的思想，先将元素排序，然后依次枚举每个元素作为“和”，利用背包 DP 统计用前面较小的元素组成该数的方案数，并累加答案。

1. 问题等价转化

• 加等式定义：集合中某个元素x xx可以表示为集合中若干个其他元素之和。注意“其他元素”不能包含x xx自身，且组合不考虑顺序（即{ a , b } \{a,b\}{a,b}与{ b , a } \{b,a\}{b,a}视为同一种）。
• 计数策略：将元素从小到大排序，依次考虑每个元素a i a_iai​。此时，所有可能参与求和组成a i a_iai​的元素一定来自a 1 ∼ a i − 1 a_1 \sim a_{i-1}a1​∼ai−1​（严格小于a i a_iai​）。如果我们能计算出用前i − 1 i-1i−1个元素组成和为a i a_iai​的不同子集个数，那么这些方案就对应以a i a_iai​为“和”的加等式。
• 子集和 DP：维护一个数组f [ v ] f[v]f[v]表示当前已考虑的元素中，选出若干元素（每个最多一次）其和恰好为v vv的方案数。顺序扫描元素，对于当前元素a i a_iai​，f [ a i ] f[a_i]f[ai​]即为组成a i a_iai​的加等式个数（由前面的元素构成）。累加后，再将a i a_iai​加入 DP 的候选集合中（更新f ff），供后续更大的元素使用。

2. 算法实现（排序 + 背包 DP）

1. 输入与排序：读取集合大小m mm和所有元素，计算元素总和s u m sumsum（用于 DP 上限）。将元素按升序排序，保证前面元素总是小于后面的。
2. DP 初始化：f [ 0 ] = 1 f[0]=1f[0]=1，其余为0 00，表示空集和为0 00的方案数为1 11。
3. 遍历元素（i = 1 ∼ m i = 1 \sim mi=1∼m）：
   • 累加答案：a n s + = f [ a i ] ans \mathrel{+}= f[a_i]ans+=f[ai​]。此时f ff仅由a 1 ∼ a i − 1 a_1 \sim a_{i-1}a1​∼ai−1​更新过，因此f [ a i ] f[a_i]f[ai​]恰好是用严格小于a i a_iai​的元素组成a i a_iai​的方案数。
   • 更新 DP：将当前元素a i a_iai​加入背包。为防止同一个元素被重复使用，需倒序更新：for j = sum down to a_i: f[j] += f[j - a_i]。
4. 输出答案：每组数据处理完后输出a n s ansans。

3. 复杂度分析

• 时间复杂度：每组数据需要进行m mm次 DP 更新，每次更新规模为O ( s u m ) O(sum)O(sum)。m ≤ 30 m \le 30m≤30，s u m ≤ 30 × 1000 = 30000 sum \le 30 \times 1000 = 30000sum≤30×1000=30000，单组复杂度约9 × 10 5 9 \times 10^59×105。共t ≤ 10 t \le 10t≤10组，总操作量不到10 7 10^7107，轻松通过。
• 空间复杂度：O ( s u m ) O(sum)O(sum)用于 DP 数组，s u m sumsum最大30000 3000030000，空间极小。

总结

巧妙地将“加等式”计数转化为有序子集和问题：排序后，每个元素作为和时，其组合只能来自更小的元素，通过背包 DP 统计组合方案数。先统计答案再更新 DP 的方式确保了当前元素不会被自己用来组合自己。该方法简洁高效，完美契合数据范围。

代码简要说明

1. 输入处理：读入t tt，对每组数据读入m mm和数组a aa，计算总和s u m sumsum，并对a aa排序。
2. DP 数组：f[30010]存储组合方案数，初始f[0]=1。
3. 核心循环：遍历排序后的a i a_iai​，先将f[a[i]]加入答案，然后倒序更新f：f[j] += f[j - a[i]]（j jj从s u m sumsum降到a i a_iai​）。
4. 输出：输出ans，每组数据后换行。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll t,m;ll a[40];ll f[30010];ll sum;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while(t--){cin>>m;sum=0;for(ll i=1;i<=m;i++){cin>>a[i];sum+=a[i];}sort(a+1,a+m+1);memset(f,0,sizeof(f));f[0]=1;ll ans=0;for(ll i=1;i<=m;i++){ans+=f[a[i]];for(ll j=sum;j>=a[i];j--)f[j]+=f[j-a[i]];}cout<<ans<<endl;}return0;}