Description
有 $n$ 张卡牌，第 $i$ 张卡牌上有一个数 $a_i$，每次可以从中选出 $k$ 张卡牌。一种选取方案的幸运值为这 $k$ 张卡牌上数的异或和。试求出所有选取方案的幸运值之和除以 $998244353$ 的余数。
Solution
看到异或，想到每一个二进制位的贡献是独立的，于是可以想到按位讨论。
再看一下 $a_i$ 的数据范围中那明显的提示，嗯是了。
于是考虑枚举这一个二进制位上选的 1 的个数，再用组合数随便计算一下即可。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <cstdio>
#define mod 998244353
#define maxN 100010
long long cnt[50];
long long inv_fac[maxN], fac[maxN], a[maxN];
long long C (long long n, long long m)
{
return fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod;
}
long long pow (long long x, long long y)
{
if(!y)
{
return 1;
}
else
{
long long dq = pow(x, y >> 1);
if(!(y % 2))
{
return dq * dq % mod;
}
else
{
return dq * dq % mod * x % mod;
}
}
}
int main ()
{
long long n = 0, k = 0;
scanf("%lld %lld", &n, &k);
for(long long i = 1;i <= n; i++)
{
scanf("%lld", &a[i]);
}
fac[0] = 1, inv_fac[0] = 1;
for(long long i = 1;i <= n; i++)
{
fac[i] = fac[i - 1] * i % mod;
inv_fac[i] = pow(fac[i], mod - 2);
}
for(long long T = 0;T <= 32; T++)
{
for(long long i = 1;i <= n; i++)
{
cnt[T] += ((a[i] & (1LL << T)) > 0);
}
}
long long Ans = 0;
for(long long T = 0;T <= 32; T++)
{
for(long long i = 1;i <= cnt[T]; i += 2)
{
long long x = i, y = k - i;
if(i > k)
{
break;
}
if(cnt[T] + y > n)
{
continue;
}
Ans += C(cnt[T], x) * C(n - cnt[T], y) % mod * (1LL << T) % mod;
Ans %= mod;
}
}
printf("%lld", Ans);
return 0;
}
|