Gym 103428B Subset

CF 传送门

首先考虑没有选出的数互不相同的限制。设 \(f_m\) 为选出 \(m\) 个 \(\in [0, n]\) 的数，异或 \(\text{popcount} = k\) 的方案数。可以考虑枚举这 \(m\) 个数和 \(n\) 的 \(\text{LCP}\)（要求后一位为 \(1\)），然后钦定一位为 \(1\) 来满足 \(\text{popcount}\) 的限制。那么就可以把这个限制扔掉了。

然后我们考虑类似反演，从 \(f\) 得到 \(g\)（注意 \(f, g\) 都是有序的），\(g_n\) 为选出 \(n\) 个 \(\in [0, n]\) 的互不相同的数，异或 \(\text{popcount} = k\) 的方案数。设 \(f_n = \sum\limits_{m = 0}^n c_{n, m} g_m\)，\(c_{n, m}\) 可以做个 dp 求出。设 \(h_{i, j}\) 为选了 \(i\) 个数，其中 \(j\) 个数出现奇数次的方案数，转移讨论第 \(i\) 个数是否出现在这 \(j\) 个数中即可。然后 \(c_{i, j} = \frac{h_{i, j}}{n^{\underline j}}\)，这里除个下降幂是因为顺序已经固定了。

答案即为 \(\frac{g_K}{K!}\)。