Count Distinct XOR Translations
Autumn Tournament (2024)
Submission name: xor-set.cpp
Problem summary
For a multiset S of L-bit integers, XOR every element by the same mask k. Count how many distinct resulting multisets exist over all masks. Multiplicities matter.
Input
n L, then n integers.
Output
The number of distinct translated multisets.
Constraints
1≤n≤100000; 0≤L≤20; 0≤x<2^L.
Worked example
Original statement sample.
Input
6 3 0 1 3 4 6 7
Output
4
Solution analysis
- Represent the multiset by its frequency array f[x]. A mask k leaves it unchanged exactly when f[x]=f[x XOR k] for every x. Such masks form a vector subspace H of the L-bit masks. Every distinct result has exactly |H| preimages, so the answer is 2^L/|H|.
- The Walsh–Hadamard coefficient at mask y is F[y]=Σx f[x]·(−1)^popcount(x AND y). Translating by k multiplies that coefficient by (−1)^popcount(k AND y). Thus a translation is a symmetry exactly when k has even dot product with every y for which F[y] is nonzero. These are exact integer coefficients; no hash or floating point is used.
- Compute F with butterfly operations (a,b)→(a+b,a−b). Insert each nonzero-frequency mask y into a binary linear basis. If their rank is r, the symmetry constraints have dimension L−r; there are 2^(L−r) symmetries and therefore 2^r distinct results.
- In the sample, frequencies are one except at 2 and 5. The nonzero spectral masks span a two-dimensional space, so the answer is 2²=4. A uniform frequency array has only coefficient F[0] nonzero and gives one result; a singleton has rank L and gives every possible shift.
Why it works
The Walsh–Hadamard transform is invertible. Therefore the translated array equals the original exactly when every transformed coefficient is unchanged. Nonzero coefficients impose precisely the stated homogeneous binary linear equations. Rank–nullity counts their solution space, and the orbit–stabilizer counting argument gives 2^rank distinct multisets.
Watch out. Do not replace multiset frequencies by booleans. Use exact signed coefficients because subtraction is essential. Coefficient zero imposes no condition; mask zero never increases rank. L=0 has one possible multiset translation.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,bits;
cin>>n>>bits;
int size=1<<bits;
vector<int>spectrum(size,0);
for(int i=0;i<n;i++){
int value;
cin>>value;
spectrum[value]++;
}
for(int length=1;length<size;length*=2){
for(int start=0;start<size;start+=2*length){
for(int offset=0;offset<length;offset++){
int a=spectrum[start+offset];
int b=spectrum[start+offset+length];
spectrum[start+offset]=a+b;
spectrum[start+offset+length]=a-b;
}
}
}
vector<int>basis(bits,0);
int rank=0;
for(int mask=1;mask<size;mask++){
if(spectrum[mask]==0){
continue;
}
int value=mask;
// A nonzero spectral mask contributes one symmetry constraint.
for(int bit=bits-1;bit>=0;bit--){
if((value&(1<<bit))==0){
continue;
}
if(basis[bit]!=0){
value^=basis[bit];
}
else{
basis[bit]=value;
rank++;
break;
}
}
}
cout<<(1<<rank)<<'\n';
}