HDU:6085 Rikka with Candies(ULL存数，位运算的应用)

位运算

HDU:6085 Rikka with Candies

题意：

$T$ 组测试样例 $(1≤T≤5)$
有 $n$ 个小朋友，$m$ 种糖果，$q$ 次询问（$1≤n,m,q≤50000$）
接下来有 $n$ 次输入表示第 $i$ 个小朋友有 $a[i]$ 的钱($1≤ai≤50000$)
接下来有 $m$ 次输入表示第 $i$ 种糖果为 $b[i]$ 的单价($1≤bi≤50000$)
接下来 $q$ 次询问，每次询问输入一个 $x$ 表示询问第 $i$ 个小朋友用自己的钱去买第 $j$ 种单价糖果剩下的钱为 $x$，满足这种条件的（$i，j$）对数。如果答案为奇数输出 $1$，偶数则输出 $0$

样例：

Sample Input
1
5 5 5
1 2 3 4 5
1 2 3 4 5
0 1 2 3 4

Sample Output
0
0
0
0
1

分析：

• 首先我们要知道 unsigned long long范围是[$0,2^{64}-1$],而LL的范围是[$-2^{63}$,$2^{63}-1$]
  题外话：遇到范围是$2^{63}$，取模$2^{64}$的这种限制条件时就要想到用unsigned long long类型。这样，如果ULL类型的整数溢出了，就相当于取模$2^{64}$了。

• 如果我们暴力的话复杂度为 $n^2$ 显然会T。所以采用ULL和位运算结合使极限复杂度降到 $n^2/64*logn$，但是每次操作的区间长度基本上都是远小于$n$的，所以实际复杂度远小于这个值。

• 思路：
  开一个二维数组a来存这个钱数是否存在过，如果存在过奇数次标记为1，偶数次标记为0；
  对于一个数x，0到x-1模上x的余数依次为0到x-1，所以直接将a的对应区间异或到ans的对应区间就可以离线处理出我们要的答案。最后对ans数组查找第x位。直接输出就OK！
  对于区间不为64整数倍，我们先将区间的r位置异或到ans的对应位置。然后不断减小r直到这个区间为64的整倍数。但是此时我们还会发现虽然此时已经是整倍数了，但并没有对齐块。此时将块往高位移动（往右）。直到移动到是整块的位置。此时a[w]则是a[0]往右移动w位的状态。将a[w]与ans异或起来就可以得出答案。

题目代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int maxn=50000+5;
ULL a[65][800],ans[800];
int b[maxn];
void setbit(ULL a[],int pos)//对a[i]的第pos位进行反转
{
    a[pos>>6]^=1ULL<<(pos&63);//a[pos/64]是分块 pos&63相当于对64取模
}
bool getbit(ULL a[],int pos)//查询对a[]的第pos位
{
    return (a[pos>>6]>>(pos&63))&1ULL;
}
void getans(int l,int r)////将a[0]的[l,r)这个区间异或到ans的[0,r-l)区间
{
    while((r-l)&63)//使区间是64整倍数
    {
        r--;
        if(getbit(a[0],r))
            setbit(ans,(r-l));
    }
    int w=0;
    while(l&63)
    {
        l++,r++,w++;
    }
    l=l>>6;
    r=r>>6;//找到对应的块
    for(int i=l;i<r;i++)
    {
        ans[i-l]^=a[w][i];
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(ans,0,sizeof(ans));
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        while(n--)
        {
            int x;
            scanf("%d",&x);
            for(int i=0;i<64;i++)
                setbit(a[i],x+i);//将a[x]表示将a[0]往高位移动x位
        }
        while(m--)
        {
            int x;
            scanf("%d",&x);
            b[x]=1;
        }
        for(int i=0;i<maxn;i++)
        {
            if(b[i])
            {
                for(int j=0;j<maxn;j+=i)
                    getans(j,min(j+i,maxn));
            }
        }
        while(q--)
        {
           int x;
           scanf("%d",&x);
           printf("%d\n",(int)getbit(ans,x));
        }
    }
    return 0;
}