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.
There are 2^(2^n) subsets of S, and a moment's thought will convince you that the xor values are uniformly distributed across the 2^n possible values. So the answer we're looking for is 2^((2^n)-n)%M. Calculating that naively (even with pow) will get you a TLE because the exponent gets excessive for large n. But, since M is prime, we can use Fermat's Little Theorem to reduce the modulus of the exponent mod M-1and wind up with values that pow can deal with in the time limit.
Number of zero-xor subsets
You are viewing a single comment's thread. Return to all comments →
There are 2^(2^n) subsets of S, and a moment's thought will convince you that the xor values are uniformly distributed across the 2^n possible values. So the answer we're looking for is 2^((2^n)-n)%M. Calculating that naively (even with pow) will get you a TLE because the exponent gets excessive for large n. But, since M is prime, we can use Fermat's Little Theorem to reduce the modulus of the exponent mod M-1and wind up with values that pow can deal with in the time limit.