HDU 6085 Rikka with Candies （bitset）

HDU 6085 Rikka with Candies （bitset）

Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:There are n children and m kinds of candies. The ith child has Ai dollars and the unit price of the ith kind of candy is Bi. The amount of each kind is infinity. Each child has his favorite candy, so he will buy this kind of candies as much as possible and will not buy any candies of other kinds. For example, if this child has 10 dollars and the unit price of his favorite candy is 4 dollars, then he will buy two candies and go home with 2 dollars left.Now Yuta has q queries, each of them gives a number k. For each query, Yuta wants to know the number of the pairs (i,j)(1≤i≤n,1≤j≤m) which satisfies if the ith child’s favorite candy is the jth kind, he will take k dollars home.To reduce the difficulty, Rikka just need to calculate the answer modulo 2.But It is still too difficult for Rikka. Can you help her?

Input

The first line contains a number t(1≤t≤5), the number of the testcases. For each testcase, the first line contains three numbers n,m,q(1≤n,m,q≤50000). The second line contains n numbers Ai(1≤Ai≤50000) and the third line contains m numbers Bi(1≤Bi≤50000).Then the fourth line contains q numbers ki(0≤ki

Output

For each query, print a single line with a single 01 digit – the answer.

Sample Input

15 5 51 2 3 4 51 2 3 4 50 1 2 3 4

Sample Output

00001

题意

A 数组有 n 个数， B 数组有 m 个数，随后有 q 个查询，每次输入一个 k ，询问有多少对 (i,j) ， 使得 Ai%Bj=k ， 输出结果模 2

思路

考虑枚举 k ，显然只有当 Bj>k,Ai>=k 时才可能满足 Ai%Bj=k

Ai%Bj=k 又等价于 Ai−k=Bj×x ，其中 x

我们用 bitset 来存放 A ，于是 bitsetA>>k 相当于 A 中所有元素减去 k ，舍弃小于 0

用 bitsetCNT 来存放 B 的倍数， bitsetCNTi=1 代表有奇数个 j 满足 i%Bj=0 ，之所以只统计奇偶数是因为最终对结果模 2

此时 bitsetA>>k 相当于 Ai−k ，然后 (bitsetA>>k)&bitsetCNT.count()&1

AC 代码

#includeusing namespace std;const int maxn = 5e4+10;bitseta,b;bitsetans,cnt;void slove(int maxK){ cnt.reset(); ans.reset(); for(int i=maxK; i>=0; --i) //枚举k { ans[i]=(cnt&(a>>i)).count()&1; //存在多少个(a-i)%b=0 if(b[i]) //枚举 i 的倍数 for(int j=0; jinline void scan_d(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'), c = getchar(); }}int main(){ int T; scan_d(T); while(T--) { int n,m,q; scan_d(n); scan_d(m); scan_d(q); a.reset(); b.reset(); int maxK=0; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。