Odd Xor Subsequences
89% Success996 Attempts50 Points1s Time Limit256MB Memory1024 KB Max Code

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:

  • \(1 \leq N \leq 10^5\)
  • \(0 \leq A_i \lt 2^{30}\)
  • \(1 \leq Q \leq 10^5\)
  • \(1 \leq K \leq N\)
Examples
Input
5
9 16 1 0 5
3
1
3
5
Output
3
4
1
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]\).

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results