【2017多校】HDU6085 Rikka with Candies

傳送門

考慮枚舉k,此時隻有bj>k,ai>=k,才可能滿足ai%bj=k

bbi={i的>k的因子屬于b[1...m]的個數}

此時餘數為k的情況數=∑ni=1bbai−k

考慮用bitset存放a,bitsetA>>k等價于a數組全部元素減去k,丢棄<0的元素

bitsetBB[i]=bbi  &  1

ans[k]=(bitsetA>>k)  &  bitsetBB.count()  &  1

求解bb,對每個bi,枚舉其倍數,O(N∑1bi)

最壞情況下變為N∗調和級數=O(N∑Ni=11N)約等于O(N∗ln(N+1))

枚舉k,對bitsetA和bitsetBB進行and操作O(N232)

是以複雜度大概O(N232+N∗ln(N+1))

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MEM(a,x) memset(a,x,sizeof(a))
#define lowbit(x) ((x)&-(x))

using namespace std;

const int N =  +;

bitset<N>a,b,ans;
bitset<N>bb;//b的倍數，bb[i]=1 : 有奇數個y滿足 i%b[y]==0

void slove(int maxK){
    bb.reset();
    ans.reset();
    for(int i=maxK;i>=;--i){//枚舉k
        ans[i]=(bb&(a>>i)).count()&;//存在多少個(a-i)%b=0
        if(b[i]){//枚舉b[i]倍數
            for(int j=;j<N;j+=i){
                bb.flip(j);
            }
        }
    }
}

int main()
{
    //freopen("/home/lu/code/r.txt","r",stdin);
    //freopen("/home/lu/code/w.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        a.reset();
        b.reset();
        int maxK=;
        for(int i=;i<n;++i){
            int x;
            scanf("%d",&x);
            a.set(x);
        }
        for(int i=;i<m;++i){
            int x;
            scanf("%d",&x);
            b.set(x);
            maxK=max(maxK,x);
        }
        slove(maxK);
        while(q--){
            int x;
            scanf("%d",&x);
            puts(ans[x]?"1":"0");
        }
    }
    return ;
}