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.

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

  • 1 ≤ T ≤ 25
  • 1 ≤ N, Q ≤ 250000
  • 0 ≤ seed < 2117566807
  • 1 ≤ mod_A, mod_V ≤ 250000
  • 1 ≤ mod_K ≤ 19
  • 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]


    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

    hide comments
    2020-02-25 17:28:38 [Rampage] Blue.Mary
    I think my AC program doesn't use FWT at all. BTW, the first line of current sample is superfluous.

    -> Thanks, copy paste mistake. Fixed now. It can be also be solved DP on subsets. I wanted to add those tags as well but for some reason I can't.

    Last edit: 2020-02-25 19:13:35
    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.