计数题小记
前言
因为是技术题，所以要寄。
[ARC146C] Even XOR
注意到题目要求是是 \(S\) 的长度为奇数子集异或和互不相同，并且 \(S⊆\{0,1,2,...,2^n-1\}\)，可得当 \(|S|>n+1\) 时，是没有贡献的。
证明：当 \(|s|= n+k,k\ge2\) 时若有贡献，则 \(S\) 要有 \(2^{n+k-1}\) 个异或和不同的奇数子集。而由题目得，每个子集的异或和取值范围是 \([0,2^n-1]\) ，两者显然矛盾。
设 \(f_i\) 为大小为 \(i\) 的合法集合个数，则显然有 \(f_0=1\ ,\ ans=\sum^{n+1}_{i=0} f_i\) 。
\(f_i\) 如何转移到 \(f_{i+1}\) ？考虑剩还有多少种元素，与大小为 \(i\) 的子集组合，即 $ \frac 1 {i+1} \times f_i (2^n - 2^{i-1}) \rightarrow f_{i+1}$ 。
值得注意的是，集合是无序的，所以每一步转移要乘上 \(\frac 1 {i+1}\) 。 code