先讲bitset用法：
1，基础
下标：\(5~4~3~2~1~0\)
数字：\(0~0~0~0~1~0\)
\(bitset\)<\(n\)> \(s\)表示一个\(n\)位的二进制数，空间复杂度：\(O(\frac{n}{32})\)，可见其非常优秀
因为其跟二进制有关，所以可以使用\(\&,|,\land\)对两个位数相同的\(bitset\)执行按位与，或，异或运算。
当然也可以使用\(<<,>>\)对其进行左移和右移
\(==,!=\)也可以比较两个位数相同的\(bitset\)代表的二进制数是否相等
2，特有的
\(s.count()\)返回二进制串中\(1\)的个数
\(s.set()\)把\(s\)的所有位变成\(1\)
\(s.set(k,v)\)或\(s[k]\)把\(s\)的第\(k\)位变为\(v\)，其中\(v\)为\(0\)或\(1\)
\(s.reset()\)把\(s\)的第\(k\)位变为\(0\)
\(s.reset(k)\)把\(s\)的第\(k\)位变成\(0\)
\(s.filp()\)或\(s=\sim s\)把\(s\)所有位取反
\(s.filp(k)\)或\(s[k]\land=1\)把第\(k\)位取反
\(01\)背包，即背包中只有\(0\)和\(1\)，一般\(f_i\)表示\(i\)这个数能否取到
正常\(01\)背包代码
f[0]=1
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]);
但是对于每个数只有选和不选的情况下
我们考虑构建\(bitset\)<\(m\)> \(s\)，其中第\(i\)位表示\(i\)能否取到
那么对于加入的\(a_i\)我们考虑我们选\(a_i\)，如果我们选\(a_i\)，那么代表原来能取到\(j\)的数，就能取到\(j+a_i\)，因为第\(i\)位表示\(i\)能否取到，所以我们选\(a_i\)能取到的值域就是\(s<<=a_i\)，不选\(a_i\)就是\(s\)，所以最终的\(s\)就是\(s=(s|(s<<=a_i))\)
代码：
bitset<m> s;
s.set(0,1);
for(int i=1;i<=n;i++)
s|=(s<<a[i]);
非常快，那么例题就可用这种优化优化到\(O(qnw),w=max(a_i)\)
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e3+50,M=3e6+50;
ll q,n,a[N],zh;
bool flag=false;
bitset<M> f,f1;
int main()
{
scanf("%lld",&q);
while(q--)
{
flag=false;
zh=0;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
zh+=a[i];
}
if(zh%n!=0)
{
puts("No");
continue;
}
zh=zh/n;
for(ll i=1;i<=n;i++)
a[i]-=zh;
for(ll i=1;i<=n;i++)
if(a[i]==0) flag=true;
if(flag)
{
puts("Yes");
continue;
}
f.reset();
f1.reset();
f.set(0,1);
f1.set(0,1);
for(ll i=1;i<=n;i++)
{
if(a[i]<0)
{
a[i]=a[i]*-1;
f=(f|(f<<a[i]));
}
else f1=(f1|(f1<<a[i]));
}
f=(f&f1);
if(f.count()>2) puts("Yes");
else puts("No");
}
return 0;
}
注意代码中\(f.count()>2\)因为\(0\)和都选一定是都能取到的，假如还有第三种能取到，那么就是\(Yes\)，否则为\(No\)