题目大意：给定n个数字，从中选中k张，求每次选出的数字的和的异或和
经验与教训：看到异或就考虑二进制
以前做过一道类似的，也是选数的题目，Blog
这个题其实也跟组合数有关，把每个数字都按二进制拆开，在对应的位置下0/1++
注意到异或的一个性质：奇数个相同的数字异或起来一定为1，偶数个相同的数字异或起来一定为0
所以我们考虑每一位的贡献一定是有奇数个1的时候才会产生贡献，但是现在选了一些个，还有一些没有选啊，为了保证这一位一定是有贡献的，所以我们要把其他的都指定为0
由于他是加和运算，这样我们抛弃了原数字是多少，因此还要乘上这一位本身的贡献
代码如下：
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
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 66, mod = 998244353;
int n, k, res;
int fac[N], ifac[N], base[66], num[66][66];
inline int ksm(int a, int b)
{
int ret = 1;
for (; b; b >>= 1)
{
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
}
return ret;
}
inline int C(int x, int y)
{
if (x < y) return 0;
if (x == y || y == 0) return 1;
return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
inline void pres_dou()
{
base[0] = 1;
for (int i = 1; i <= 32; ++ i) base[i] = base[i - 1] * 2 % mod;
fac[0] = fac[1] = 1;
for (int i = 2; i <= n; ++ i) fac[i] = fac[i - 1] * i % mod;
ifac[n] = ksm(fac[n], mod - 2);
for (int i = n - 1; i >= 0; -- i) ifac[i] = ifac[i + 1] * (i + 1) % mod;
return;
}
signed main()
{
n = read(), k = read();
for (int i = 1; i <= n; ++ i)
{
int x = read();
for (int j = 0; j <= 32; ++ j)
{
int c = (x >> j) & 1;
++ num[j][c];
}
}
pres_dou();
for (int i = 0; i <= 32; ++ i)
{
for (int j = 1; j <= min(num[i][1], k); j += 2)
{
res = (res + C(num[i][1], j) * C(num[i][0], k - j) % mod * base[i] % mod) % mod;
}
}
put(res);
return 0;
}
|
总结：
这次考试心态不好，以后要逐步改善
第一题应该切掉，没有深入思考，这是我的过错
第二题感觉是个贪心，但是没时间细想了，因为写暴力耽误了时间
第三题数据水，直接切掉了，但是正解的话，要用并查集来维护一下这个图，维护这个点之后最早能达到的点
期望得分：30+20+50=100pts，实际得分：30+20+100=150pts
暴力分终归打满了，但是正解要仔细思考呀