www.luogu.com.cn
https://www.luogu.com.cn/problem/P9509
简化一下题意，对于原集合 SS，就是找原集合的两个子集 S1,S2S_1,S_2，使得 S1∪S2=S,S1∩S2=∅S_1 \cup S_2 = S,S_1 \cap S_2 = \empty，S1,S2S_1,S_2 的平均数等于 SS 的平均数
注意到特殊性质中的 ∑ai=0\sum a_i = 0，这个很好写，分成一个正集合和一个负集合，每个跑一个可行性背包 f,gf,g，fi,gif_i,g_i 表示 S1,S2S_1,S_2 中能否存在 ii，如果 fi=gi，i∈[1,f_i = g_i，i \in [1, ∑aj2\sum a_j \over 2 (aj>0))(a_j > 0))，那么S1,S2S_1,S_2 的平均数等于 SS 的平均数
考虑把整体情况转化，把 aia_i 减掉平均数，那么 ∑ai=0\sum a_i = 0，这样就成了特殊性质。按照特殊性质的方法处理就行。
但时间复杂度是 O(n2k)O(n^2k)(kk 是值域，题中为 5×1035\times 10^3)，大约是个 5×1095 \times 10^9，会炸，考虑用 bitset 优化可行性背包，f = f|=(f<<a_i)，时间复杂度优化到了 10810^8 左右，可以通过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,a[N];
bitset<2500000> fp,fn;
void solve(){
int sum=0,agv=0;
fp=fn=0;
vector<int> nn,pp;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],agv+=a[i];
if(agv%n!=0){
puts("No");
return;
}
agv/=n;
for(int i=1;i<=n;i++){
a[i]-=agv;
if(a[i]==0){
puts("Yes");
return;
}
(a[i]>0?pp:nn).push_back(abs(a[i]));
sum+=(a[i]>0?a[i]:0);
}
fp[0]=fn[0]=1;
for(int x:pp) fp|=(fp<<x);
for(int x:nn) fn|=(fn<<x);
fp[sum]=fn[sum]=fp[0]=fn[0]=0;
puts(((fp&fn)!=0?"Yes":"No"));
}
signed main(){
cin.tie(0)->ios::sync_with_stdio(0);
int q;cin>>q;
while(q--) solve();
return 0;
}