You are viewing a single comment's thread. Return to all comments →
Finally got AC by DP, some of my thoughts here:
Note the uppper bound of N is 1e5, it tells us to come up with a linear or NlogN solution for each case, but I failed.
So let's look at the range of a[i], it's in [3500, 4500], much smaller than range of N, furthermore, the XOR of any multiset must be in range [0, 8191] (8191==2^13-1). These two observations are the key to my DP solution:
Count the number of each unique integer in input array, then for each unique number, I enumerate every possible integer in [0, 8191] and do some simple calculation to get the number of multiset.
The time complexity of my DP solution is O(M*P), M is the number of unique input integers, P is the range of possible XOR sum, so the upper bound of N*M is 1e7, quite resonable.