We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Prime XOR
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.