www.luogu.com.cn
https://www.luogu.com.cn/problem/P9509
简化一下题意，对于原集合 ，就是找原集合的两个子集 ，使得 ， 的平均数等于 的平均数
注意到特殊性质中的 ，这个很好写，分成一个正集合和一个负集合，每个跑一个可行性背包 ， 表示 中能否存在 ，如果 ，那么 的平均数等于 的平均数
考虑把整体情况转化，把 减掉平均数，那么 ，这样就成了特殊性质。按照特殊性质的方法处理就行。
但时间复杂度是 ( 是值域，题中为 )，大约是个 ，会炸，考虑用 bitset 优化可行性背包，f = f|=(f<<a_i)，时间复杂度优化到了 左右，可以通过。
#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;
}