2019牛客暑期多校训练营(第一场)


链接


Problem A

Solved by Water_sheep. 00:22 (+)

题意:

题解:


Problem B

Upsolved by purple_bro.

题意:

题解:


Problem C

Unsolved.


Problem D

Unsolved.


Problem E

Solved by Robin_Lo. 01:47 (+)

题意:

题解:


Problem F

Solved by Water_sheep. 01:09 (+1)

题意:

题解:


Problem G

Unsolved.


Problem H

Upsolved by purple_bro.

题意:

  • 给一个长度为 $n$ 的序列,求所有异或和为 0 的子集大小之和,$\pmod{1e9 + 7}$。

题解:

  • 求出这个序列的线性基,假设有 $r$ 个基,由线代知识可知,这个序列能构成 $2^{n - r}$ 个子集异或和为 0。
    • 考虑不在基里面的一个数,被选中的情况就有 $2 ^ {n - t - 1}$ 种,所以贡献就为 $(n - r) \times 2 ^ {n - t - 1}$。
    • 考虑基内的数的贡献,我们知道基外的数可以由若干个基组成,换言之就是一个数可以换成若干个基,现在我们不用关心由多少个基构成,只要关心这个基是否参与构成。这样就 for 一边线性基,如果这个基参与构成,答案就加上 $2 ^ {n - t - 1}$。
  • 复杂度 $O(60n)$。

Problem I

Unsolved.


Problem J

Solved by Water_sheep. 00:09 (+)

签到题。