DCOJ - 长乐一中命题Day2

再见了，所有的 。

被 吊打了，大概是没时间了补题了，所以直接写博客来了。

A. 按位或（or）

题目简介

存在一个长度为 的非负数序列 ，满足 ，且

$$\operatorname{or}\limits_{i=1}^{n}x_i=t$$

求出满足上述条件的序列的总数，对 取模。

数据范围：

暴力转移是 ，四舍五入是 。

考虑 特别小的情况下怎么做：定义集合 表示 的或子集，即所有满足 的 。那么可以直接计算 个数或起来的子集的方案数，可以对 容斥。时间复杂度 。

所以我们想到容斥（我怎么想不到），根据 的特殊性质，所以我们只需要计算 的子集中为 的倍数的数量。

容易发现 ，所以我们按照余数划分类。枚举容斥中 的位中 分别有多少个 。

用 表示当前考虑了前 位，此时 为 的方案数，然后容斥做。

时间复杂度 。

---

题面

---

官方题解

---

补充题解

找到了一个原场，可以在这里面看题解。

链接：https://www.cnblogs.com/hzoi-wsn/p/15500854.html