XNOR's Rebellion
Time limit1sMemory limit1024 MB
Given N numbers of B bits, pick a nonempty subsequence and fold it with B-bit XNOR from left to right to maximize the result.
- Level
Medium6 of 10
- Topics
- Bit manipulation, Dynamic programming, Hash map
- Solved
- No attempts yet
Problem
Competitive programming problems always use only XOR, and XNOR is furious about it. It decides to start a rebellion by gathering non-negative integers!
XNOR is methodical, so before starting the rebellion it wants to calculate its strength first. Since this is XNOR's rebellion, the strength is the result of applying XNOR to the given numbers in order from the front. Every integer XNOR gathered can be written as an unsigned -bit integer, so XNOR uses XNOR on -bit integers.
A higher strength means a higher chance of success, so XNOR picks one or more of the numbers to maximize the strength. The order of the chosen numbers cannot be changed.
Input
The first line contains , the number of integers XNOR gathered, and , the number of bits XNOR uses, separated by a space. (; )
The second line contains the non-negative integers in decimal form, separated by spaces. ()
Output
Print the maximum strength of the rebellion that XNOR can produce on the first line.
Hint
The bitwise XNOR of two numbers converts both to binary and compares each bit. The result bit is if the two bits match and if they differ. For example, .