ANDQQ - AND Queries
Given an array A of N integers, you are required to solve Q queries. Each query consists of a positive integer V and a non-negative integer K. For each query, find out how many numbers in the array A have exactly K common one bits with the number V.
In other words, for each query, you need to calculate how many numbers are there in the array such that Ai & V have exactly K bits set in its binary representation, where & denotes the bitwise AND operation.
Note that since the input can be huge, they will be generated randomly using a pseudorandom generator, whose parameters will be given as input. Also for similar reasons, it is not required to output the result for every query, rather compute the sum of this value for all queries and output this sum. More specifically, for the i-th query, let Ci be the count of integers in A having exactly K common one bits with Vi. Then it is required to output the sum of all Ci only.
Note that the seed is a global variable which gets updated after each random call, with the initial value being given as input.1 ≤ T ≤ 25
1 ≤ N, Q ≤ 250000
0 ≤ seed < 2117566807
1 ≤ mod_A, mod_V ≤ 250000
1 ≤ mod_K ≤ 19
A = [2, 3, 0, 1, 1, 2, 2, 3, 1, 0]
V = [2, 0, 3, 1, 0, 0, 2, 0, 0, 1]
K = [0, 2, 1, 1, 1, 2, 2, 0, 2, 2]
C = [5, 0, 6, 5, 0, 0, 0, 10, 0, 0]
In other words, for each query, you need to calculate how many numbers are there in the array such that Ai & V have exactly K bits set in its binary representation, where & denotes the bitwise AND operation.
Note that since the input can be huge, they will be generated randomly using a pseudorandom generator, whose parameters will be given as input. Also for similar reasons, it is not required to output the result for every query, rather compute the sum of this value for all queries and output this sum. More specifically, for the i-th query, let Ci be the count of integers in A having exactly K common one bits with Vi. Then it is required to output the sum of all Ci only.
Input
The first line contains an integer T, denoting the number of test cases. Each test case contains six space separated integers in the order: seed, N, Q, mod_A, mod_V, mod_K. Afterwards, the input for each test case will be generated as described by the python code below.def random(): global seed seed = (seed * 997 + 29) % 2117566807 return seed A = [0 for _ in range(N)] for i in range(N): A[i] = random() % mod_A V = [0 for _ in range(Q)] K = [0 for _ in range(Q)] for i in range(Q): V[i] = random() % mod_V K[i] = random() % mod_K
Note that the seed is a global variable which gets updated after each random call, with the initial value being given as input.
Constraints
Output
For each test case, output the case number followed by the required output. Please refer to the sample input/output section for more clarity of the format.Sample Input
2 1 10 10 4 4 3 0 100 1000 10000 100000 10
Sample Output
Case 1: 26 Case 2: 10260
Explanation
For the first case:A = [2, 3, 0, 1, 1, 2, 2, 3, 1, 0]
V = [2, 0, 3, 1, 0, 0, 2, 0, 0, 1]
K = [0, 2, 1, 1, 1, 2, 2, 0, 2, 2]
C = [5, 0, 6, 5, 0, 0, 0, 10, 0, 0]
hide comments
[Rampage] Blue.Mary:
2020-02-25 17:28:38
I think my AC program doesn't use FWT at all. BTW, the first line of current sample is superfluous.
|
Added by: | sgtlaugh |
Date: | 2020-02-24 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own Problem Used in ACM ICPC Yangon 2018 |