把 0~2^n-1 划分为若干组使得每组异或和为 0 November 6, 2019 把 $$0$$~$$2^n-1$$ $$(n\ge 2)$$ 划分为若干组使得每组异或和为 0，最多分出多少组？ 显然组数的上界是 $$\lceil\frac{n}{3}\rceil$$。 可以递归构造： ```python def gen(n): if n==2: return [(0,),(1,2,3)] if n==3: return [(0,),(1,2,3),(4,5,6,7)] s=gen(n-2) res=[(0,),(1,2,3)] for i in s: if len(i)==3: key=[0,2,3,1] for j in range(4): res.append((i[0]<<2|j,i[1]<<2|key[j],i[2]<<2|key[key[j]])) elif len(i)==4: t=2**(n-1) res.append((t,t+1,t+2,t+3)) res.append((4,t+9,t+13)) res.append((5,t+11,t+14)) res.append((8,t+7,t+15)) res.append((10,t+6,t+12)) res.append((12,t+4,t+8)) res.append((15,t+5,t+10)) if ~n&1: return res res2=[] for i in res: if set(i)!={4,8,12} and set(i)!={5,10,15}: res2.append(i) return res2 ```
銧祠