【牛客算法周练2】B

题意有t个样例，每个样例是给你n个数，问你能不能凑出来3600的倍数。
那么这道题属于是背包问题，就是看每个数能不能取到。
这里提供用bitset的一种做法（比较厉害），bitset上面每个数代表这个数能不能被取到，当然我们首先会对所有的a[i]取模3600，这样的话，每个a[i]都在0-3599范围里，
具体 我们考虑每一个a[i]的时候，答案只可能增多或者不变，因此使用|或运算符就可以，但是我们还要特别考虑的是溢出问题，因为你可能向右右移了a[i]位之后溢出了，那么我们就在|上一个向左移3600位的结果，就可以确保万无一失，然后就快乐ac啦~~

#include<bits/stdc++.h>
using namespace std;

int a[100010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],a[i]%=3600;
        bitset<7500> dp;
        for(int i=1;i<=n;i++)
        {
            dp|=(dp<<a[i])|((dp<<a[i])>>3600);
            dp[a[i]]=1;
        }
        if(dp[0]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}