RainAir
My OI Blog
RainAir
「CF388D」Fox and Perfect Sets

题意

定义一个集合 $S$ 是好的,当且仅当:
1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$,这里 $\oplus$ 是异或操作。
2. 集合最大值 $\leq n$

求这样的集合的个数,模 $10 ^9+7$

题解

这是个好题(至少我觉得我是想不出来)
首先一个观察是这样的集合一定是由一组线性基生成出来的,我们只需要搞出一个让线性基和集合的一一对应关系,就可以很方便的 dp 了。
我们考虑用线性基求最大异或和的时候,我们需要使用高斯消元每次选取出第一位非 $0$ 位最靠前的那一个向量,去消掉这一位上其他的 $1$,如果有的变成 $0$ 了说明能被线性组合出来不合法。观察消元后的线性基,我们可以发现存在一些列只有一个 $1$(主元列),我们对这个结果进行计数。
数位 $dp$ :设 $f_{i,j,lim}$ 表示从高往低考虑到第 $i$ 位,已经用了 $j$ 个向量去限定,现在是否卡上界。分类讨论:
1. 不卡上界
考虑这一位可以使用一个单独的向量限定为 $1$,也可以在已经有的向量里限定。
如果开一个单独的向量那么必须钦定目前已有的向量这一位都是 0,就是 $f_{i-1,j+1,0}$ 种方案。
如果这一位用之前的向量限定,那么每个向量这一位都可以填 $0$ 和 $1$,就有 $f_{i-1,j,0}*2^j$ 种方案。
2. 卡上界
这里和上面唯一不同的地方就是我们需要求出限定这一位为 $0/1$ 的方案。由于最大值是所有向量异或起来,那么如果这一位有奇数个 $1$ 那么这一位就是 $1$,否则就是 $0$,方案数都是 $2^{j-1}$。但是如果之前还没有基这一位就只能是 $0$ 需要特判一下(

代码

挺好写的

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/843
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF388D」Fox and Perfect Sets
题意 定义一个集合 $S$ 是好的,当且仅当: 1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$,这里 $\oplus$ 是异或操作。 2. 集合最大值 $\leq n$ 求这样的集合的个数,模 $10 ^9…
扫描二维码继续阅读
2019-10-08
标签
近期评论