题目名称：音乐问题 问题描述： 强迫症患者HH只有在歌曲结束时处于整点时间（即分钟和秒均为0）才能停止听歌 他初始时间为12:00:00，且一旦开始听歌就只能通过满足上述条件的方式停止 给定若干首歌曲的时长，请判断是否存在一种选歌方式（每首歌最多选一次），使得HH能在某个整点时间停止听歌。

输入描述： 第一行包含一个正整数 T（1 ≤ T ≤ 60），表示测试用例的数量。 每个测试用例包含两行：

第一行是一个整数 n（1 ≤ n < 10⁵），表示歌曲数量。

第二行包含 n 个整数 a₁, a₂, ..., aₙ（1 ≤ aᵢ ≤ 10⁶），表示每首歌曲的时长（单位：秒）。 输出描述： 对于每个测试用例，输出一行 "YES" 或 "NO"，表示是否存在符合条件的选歌方式

对于1e5的数据与1e9的时长。。。。。

常规方法是用一个dp[n]来说明余数为n的有几个（有没有），能想到这个主要是因为这个很容易得出状态转移来：假设有1000，2000，3000。1000加入，dp[1000]为1，之后2000加入，dp[2000]为1，遍历有dp[1000]为1，那么dp[3000]也为1

不难看出，对于每一个我们都需要遍历一遍看原来有没有，时间复杂度就是极高的O（T * n * 3600），实际上有很多操作都是没有必要的，这里有两个很有效的优化方法：

1：鸽巢原理的使用

结论就是：对于任意个含n个正整数的数列，一定至少有一个子集有其sum%n==0

证明也很简单，设前缀和为Si = a1+a2+......+ai，对每个Si取MOD，也就是有可能为0,1,2......n-1——鸽巢原理则必然会有两个前缀和对应的余数是一样的。如果就是0，那最好。如果不是0，那么这两个前缀和相减就可以了

修补骑士不擅长数学，大家看个乐呵就可以了。这也就说明了本题只要是n>=3600的都可以直接输出YES

2：bitset的运用

botset真是个好东西吧，位运算的高速性决定了他在时空上都很有优势

结合代码讲解一下具体是怎么使用的：

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

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int T; 
    
    cin >> T;
    
    for(int t = 0;t < T;t++)
    {        
        bitset<8888> bs;
        
        int n,x;
        
        cin>>n;
        
        vector<int> num(n,0);
        
        for(int r = 0;r <n;r++)
        {
            cin>>num[r];
        }
        
        if(n >= 3600)
        {
            cout<<"YES"<<endl;
            
            continue;
        }
        
        for(int r = 0;r < n;r++)
        {
            x = num[r];
            
            x = x % 3600;
            
            bs |= (bs << x) | (bs >> (3600 - x));
            
            bs[x] = 1;
        }
        
        if(bs[0] == 1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    
    return 0;
}

关于位运算基础大家可以去找点视频看看，这里讲解最关键的步骤：bs |= (bs << x) | (bs >> (3600 - x));

左边的bs<<x，也就是假设有某一位bs[j] = 1（余数为j的存在），那么左移后就是bs[j + x] = 1，与我们写暴力背包的思路完全相同

另外一边的右移有些出乎意料，首先我们对于x取模，之后对于3600 - x，所有小于这个的会变成负数不用管，大于这个的，就说明他加上x后会变成超过3600的数字，我们就需要减少3600 - x来完成近似取模的操作（这个可以自己打个表，当然最重要的还是要提前取模）

不要忘记对于自己要单独标注出来，之后用|把所有1位次合并拿到就可以了

所以说bitset真是个好东西吧，在动态规划里真的很常用，大家闲的没事干可以把自己用常规方法写出来的DP又用bitset优化来写一遍，就算这不是必要的，也可以加深印象。毕竟，学算法，要看也要敲啊（笑）