Odd Xor Subsequences

★★★★★

4.3

3 votes

Fourier Transformations, Linear Algebra, Math, Mathematics, Bit manipulation, Fast Fourier transform, Combinatorics

Details

Problem

Problem:

You are given a sequence $A$ of size $N$ and $Q$ queries. For each query:

You are given an integer $K$ .
Your task is to count the number of subsequences of $A$ of size $K$ such that Bitwise Xor Sum of elements of the subsequence is odd. Since the answer can be large, compute it modulo $998, 244, 353$ .

Note: Bitwise Xor Sum of a sequence is Bitwise XOR of its elements.

Input Format:

The first line of the input contains a single integer $N$ .
The second line of the input contains $N$ space-separated integers $A_1, A_2, ..., A_N$ .
The third line of the input contains a single integer $Q$ .
$Q$ lines follow. Each of these lines contains a single integer $K$ describing a query.

Output Format:

For each query, print a single line containing one integer ― the count of subsequences of $A$ of size $K$ having odd Bitwise Xor Sum modulo $998, 244, 353$ .

Constraints:

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For query $1$ , $K = 1$ . The subsequences of $A$ of size $1$ that satisfy the condition given in the problem are $[9], [1]$ and $[5]$ .
For query $2$ , $K = 3$ . The subsequences of $A$ of size $3$ that satisfy the condition given in the problem are $[9, 16, 0], [16, 1, 0], [9, 1, 5]$ and $[16, 0, 5]$ .
For query $3$ , $K = 5$ . The subsequence of $A$ of size $5$ that satisfy the condition given in the problem is $[9, 16, 1, 0, 5]$ .