Luogu 7526

题目大意

给定 $n$ 个数 $a_i$，对于每一个 $i\in[0,K-1]$，求选出 $m$ 个数使得异或和为 $i$ 的方案数。

$m\le n\le 1.3\times 10^5, a_i<K\le 2^{17}$。

题解

设 $\mathcal F:\mathbb R^K\to\mathbb R^K$ 表示异或的沃尔什变换，设答案的形式幂级数为 $G$，$a_i$ 的形式幂级数为 $F_i$，$a$ 的形式幂级数为 $A$，则
$$
\mathcal F(G)[k]=\sum_{S\subset [n],|S|=m}\prod_{i\in S}\mathcal F(F_i)[k]=\sum_{S\subset [n],|S|=m}\prod_{i\in S}\mathcal (-1)^{|a_i\cap k|}
$$
注意到右边的和式只与 $\mathcal F(A)[k]$ 相关，考虑对于任意 $k$，令
$$
\mathcal F(A)[k]=\sum_{i=0}^{K-1}(-1)^{|i\cap k|}A[i]=c_1-c_2
$$
其中 $c_1$ 表示 $(-1)^{|i\cap k|}$ 取到 $1$ 时的和，$c_2$ 表示取到 $-1$ 的和，显然有 $c_1+c_2=n$。则原答案右边的和式对答案有正的贡献当且仅当从 $c_1$ 选一些数，$c_2$ 中选一些数，其中从 $c_2$ 选的数的个数一定是偶数，且一共选了 $m$ 个数，写成生成函数即为
$$
[x^m] (1+x)^{c_1}(1-x)^{n-c_1}
$$
展开得到
$$
[x^m]\sum_{i=0}^{c_1}\binom{c_1}{i}x^i\sum_{j=0}^{n-c_1}\binom{n-c_1}{j}(-1)^{n-c_1-j}x^{n-c_1-j}
$$
套路交换枚举顺序，有
$$
\begin{aligned}
&[x^m]\sum_{i=0}^nx^i\sum_{j=0}^{\min\{c_1,i\}}\binom{c_1}{j}\binom{n-c_1}{i-j}(-1)^{n-c_1-i+j}\\
=&\sum_{i=0}^{\min\{c_1,m\}}\binom{c_1}{i}\binom{n-c_1}{m-i}(-1)^{n-c_1-m+i}\\
=&(c_1)!(n-c_1)!\sum_{i=0}^{\min\{c_1,m\}}\frac{(-1)^{n-c_1-m+i}}{i!(c_1-i)!(m-i)!(n-c_1-m+i)!}
\end{aligned}
$$
NTT 不难解决，时间复杂度 $\mathcal O(n\log n+K\log K)$

int n, m, K;
std::cin >> n >> m >> K;
std::vector<Int> fac(n + 1, 1), inv(n + 1);
for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
inv[n] = Int(1) / fac[n];
for (int i = n; i >= 1; --i) inv[i - 1] = inv[i] * i;
Poly a(m + 1), b(n - m + 1);
for (int i = 0; i <= m; ++i) {
	a[i] = inv[i] * inv[m - i];
	if ((m - i) & 1) a[i] = Mod - a[i];
}
for (int i = 0; i <= n - m; ++i) b[i] = inv[i] * inv[n - m - i];
a = a * b;
for (int i = 0; i <= n; ++i) a[i] *= fac[i] * fac[n - i];
std::vector<Int> f(K), g(K);
for (int i = 0, x; i < n; ++i) std::cout >> x, f[x] += 1;
FWT(f, false);
for (int i = 0; i < K; ++i) g[i] = a[(n + f[i]) / 2];
FWT(g, true);
for (int i = 0; i < K; ++i) std::cout << g[i].x << " ";

剩下的 2 分就要各显神通了