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 nonnegative 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 A_{i} & 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 ith query, let C_{i} be the count of integers in A having exactly K common one bits with V_{i}. Then it is required to output the sum of all C_{i} 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 A_{i} & 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 ith query, let C_{i} be the count of integers in A having exactly K common one bits with V_{i}. Then it is required to output the sum of all C_{i} 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:
20200225 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:  20200224 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own Problem Used in ACM ICPC Yangon 2018 