sum

The first line of the input has an integer T ( 1≤T≤10 ), which represents the number of test cases.
For each test case, there are two lines:
1.The first line contains two positive integers n, m ( 1≤n≤100000 , 1≤m≤5000 ).
2.The second line contains n positive integers x ( 1≤x≤100 ) according to the sequence.

  
  

   
   2
3 3
1 2 3
5 7
6 6 6 6 6
  
  

  
  

   
   YES
NO
  
  

当n>=m 时一定yes

当n<m时候若pre[1...i]%m==pre[i...j]%m或者pre[1...i]%m==0    (1<=i<j<=n)

#include"iostream"
#include"cstdio"
using namespace std;
const int maxn=100000*4;
int upper;
int tree[maxn];
int visit[maxn];

int lowbit(int x)
{
    return x&(-x);
}


void init()
{
    upper=0;
    memset(tree,0,sizeof(tree));
}


void update(int r,int x)
{
    while(r<=upper){tree[r]+=x;r+=lowbit(r);}
}

int sum(int r)
{
    __int64 res=0;
    while(r)
    {
        res+=tree[r];
        r-=lowbit(r);
    }
    return res;
}


int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);

        memset(visit,0,sizeof(visit));
        init();
        upper=n;

        /*cout<<"n:"<<n<<endl;*/


        int flag=0;
        for(int i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            update(i,a);
            
            int mod=sum(i)%m;
            if(!mod)
                flag=1;
            if(!visit[mod])
                visit[mod]=1;
            else
                flag=1;
        }
        if(n>=m)
        {
            printf("YESn");
        }
        else
        {
            /*for(int i=1;i<=n;i++)
                cout<<sum(i)<<endl;*/
            if(flag)
                printf("YESn");
            else
                printf("NOn");
        }

    }
    return 0;
}

最后

以上就是可靠火龙果为你收集整理的HDOJ 5776 树状数组sum的全部内容，希望文章能够帮你解决HDOJ 5776 树状数组sum所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。