Odd Xor Subsequences
Practice
4.3 (3 votes)
Fourier transformations
Linear algebra
Math
Mathematics
Bit manipulation
Fast fourier transform
Combinatorics
Problem
89% Success 996 Attempts 50 Points 1s Time Limit 256MB Memory 1024 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\)
Sample Input
5 9 16 1 0 5 3 1 3 5
Sample 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]\).
Code Editor
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
Submissions
Please login to view your submissions
Similar Problems
Points:50
7 votes
Tags:
ArraysLinear AlgebraImplementationFast Fourier transformCombinatoricsFourier TransformationsModular exponentiationMathematicsModulo arithmeticMath
Points:50
Tags:
Linear AlgebrafftFast Fourier transformHardMathematics
Points:50
Tags:
Modular arithmeticLinear AlgebraHardFast Fourier transformNumber TheoryMathematics
Editorial
Login to unlock the editorial
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