HDU 5776 Sum-白红宇

HDU 5776 Sum

阅读量：5358 次

发布时间：2019-06-15

本文共 831 字，大约阅读时间需要 2 分钟。

题意：问是否存在序列n的某子序列之和是m的倍数

首先求每位%m后的前缀和【 (a+b)%k == (a%k +b%k)%k】， a[i]=(a[i]+a[i-1])%m，若出现余数为0，则子序列存在

统计每个余数出现的次数，若出现两个相同余数即a[k] == a[i] k>i, 或n>m（抽屉原理：m个数放进m-1个抽屉必有两个数在同一个抽屉里）则子序列i+1...k必是m的倍数

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;typedef pair
                  
                    p;typedef long double ld;#define mem(x) memset(x, 0, sizeof(x))#define me(x) memset(x, -1, sizeof(x))#define fo(i,n) for(i=0; i
                   
                    >t; while(t--) { cin>>n>>m; mem(vis); ll f=0; for(i=1; i<=n; i++) cin>>a[i], a[i]+=a[i-1]; if(n>m) { cout<<"YES"<
                    
                     1 || !a[i]) f=1; } if(f) cout<<"YES"<