题目大意

给定 $n$ 个数，求出选 $k$ 数的异或和之和，模 $998244353$。

分析

对于每一二进制位，肯定只有异或值为 $1$ 才有贡献，那么就枚举这一位上取 $1$ 的个数为 $x$，那么取 $0$ 的个数对应地就为 $k-x$，这一位的贡献就为 $\binom{\text{count}(1)}{x}\cdot\binom{\text{count}(0)}{k-x}$。

代码

const int N = 1e5 + 10;
const int mod = 998244353;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, m;
ll a[N], mx;
ll qpow(ll a, int b) {
	ll ans = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) ans = ans * a % mod;
	return ans;
}

ll prod[N], invp[N], ans;
ll C(int n, int m) {
	if (n < m) return 0;
	return prod[n] * invp[m] % mod * invp[n - m] % mod;
}

int main() {
	freopen("card.in", "r", stdin);
	freopen("card.out", "w", stdout);
	n = Read(), m = Read();
	for (int i = 1; i <= n; i++) a[i] = Read(), mx = max(a[i], mx);
	prod[0] = 1;
	for (int i = 1; i <= n; i++) prod[i] = prod[i - 1] * i % mod;
	invp[n] = qpow(prod[n], mod - 2);
	for (int i = n - 1; i >= 0; i--) invp[i] = invp[i + 1] * (i + 1) % mod;
	for (ll j = 1; j <= mx; j <<= 1) {
		int cnt0 = 0, cnt1 = 0;
		for (int i = 1; i <= n; i++)
			if (a[i] & j) cnt1++;
			else cnt0++;
		for (int i = max(m - cnt0 + ((m - cnt0) % 2 == 0), 1); i <= min(cnt1, m); i += 2) {
			(ans += C(cnt1, i) * C(cnt0, m - i) % mod * j % mod) %= mod;
		}
	}
	printf ("%lld\n", ans);
	return 0;
}