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 的子集大小之和,(mod1e9+7)

题解:

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

Problem I

Unsolved.


Problem J

Solved by Water_sheep. 00:09 (+)

签到题。