「Codeforces」D. Infinite Set

D. Infinite Set

https://codeforces.com/contest/1635/problem/D

题目描述

你有一个由不同正整数组成的数组和一个无限集 S，现在你需要往集合 S 中塞入所有符合 $x$ 条件的数。

$x$ 的条件（满足其中任意一个即可）：

1. $x=a_i(1\le i\le n)$
2. $x=2y+1(y\in S)$ （$y$ 必须在 S 集合中）
3. $x=4y(y\in S)$ （$y $ 必须在 S 集合中）

求无限集 S 中所有小于 $2^p$ 的个数。

输入描述

第一行包含两个整数 n 和 p (1≤n,p≤2⋅10⁵)。

第二行包含 n 个整数 a1,a2,…,an (1≤ai≤10⁹)。

保证 a 中的所有数字都是不同的。

输出描述

打印一个整数，即 S 中严格小于 2p 的元素数。 请记住以 10⁹+7 为模打印。

样例

#1

2 4
6 1

9

#2

4 7
20 39 5 200

14

#3

2 200000
48763 1000000000

448201910

提示

在第一个示例中，小于 2⁴ 的元素是 {1,3,4,6,7,9,12,13,15}。

在第二个例子中，小于 2⁷ 的元素是 {5,11,20,23,39,41,44,47,79,80,83,89,92,95}。

解析

有一说一，二进制的题目我确实没写过…，一时间也只能想到暴力，可这样不可能过，后面看大佬题解，发现要用二进制…

**Tips：**以后但凡看到这种 $2^p$ 次幂的形式，要往二进制想想。

根据二进制，$x$ 的第二和第三条件可以转为：

1. 第一条件其实就是 A 数组的所有元素均属于 S
2. $2x+1$ 相当于 $2<<1$ 然后加 $1$ （向后添加一个 1）
3. $4x$ 相当于 $4<<2$ （向后添加两个 0）

题目要我们求 S 中所有小于 $2^p$ 的数，其实就是求对应的二进制最高位 1 的后面 0 的变化，例如 $p=3$ 时，对应二进制为 $1000$ ，我们可以得到且不保证符合的有 $0000、0100、0110、0111、0010、0011、0001$ 。

通过上面的例子，我们发现，只是 1 后面的 0 发生了变化，而我们的规则是要么增加一个 1，要么增加两个0（这0是一起添加的，不能分开）。

我们假设一个数为 $x$ ，那么我们可以得到：

$x$ 增加位数	得到的不同的数
0	$x$	1
1	$x1$	1
2	$x00、x11$	2
3	$x001、x100、x111$	3
4	$x0000、x1100、x0011、x1111、x1001$	5

上表意思：一个数的二进制在其后面增加若干位数，每次只能增加一个 1 或两个 0 ，那么最终得到的不同的数有多少个。

并且能发现，无论如何变化，它们都保证是唯一的。

看得出来这是个斐波那契数列 $F[i]=F[i-1]+F[i-2]$ ，这里表示一个数增加 $i$ 位可以得到的不同数的数量为 $F[i]$ 个。

我们现在只是求了一个数增加若干位若得到的不同数，并没有将前面的也算进来，所以还需要对其做一个前缀和 $prefix[i]=prefix[i-1]+F[i]$ ，此时定义变为 $prefix[i]$ 表示增加 $i$ 位后所得到的所有不同数。

最后需要注意若一个数 $a_i$ 可以由另外一个数得到 $a_j$ ，因此为了不重复计算，所以只保留 $a_i$ ，例如 A 有 2, 8 两个元素，8 可以通过 2 得到，因此我们只保留 2 即可。

2：0010

8：1000

0010 可以通过一次变化（即在尾部加两个 0 ）==> 001000 ==> 1000

AC Code

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));public static void main(String[] args) throws Exception {final int MOD = 1000000000 + 7;final int MAX = 200005;int n = nextInt(), p = nextInt(), ans = 0;int[] A = new int[MAX];int[] F = new int[MAX];int[] prefix = new int[MAX];F[0] = F[1] = 1;prefix[0] = 1; prefix[1] = 2;HashMap<Integer, Boolean> map = new HashMap<>();for(int i = 2; i < MAX; i++) {F[i] = (F[i-1] + F[i-2]) % MOD;prefix[i] = (prefix[i-1] + F[i]) % MOD;}for(int i = 1; i <= n; i++) {A[i] = nextInt();map.put(A[i], true);}// 对数组元素进行去重for(int i = 1; i <= n; i++) {int x = A[i];while(x != 0) {if(x % 2 == 1) x >>= 1; // 条件2，末尾加 1else if(x % 4 == 0) x >>= 2; // 条件3，末尾加两个 0else break;if(map.containsKey(x)) { // 判断 x 是否已经存在 S 中map.remove(A[i]); // 若存在，则表示 A[i] 可以通过其它元素得到，估抛弃该元素break;}}}Set<Integer> set = map.keySet();for(Integer x : set) {int bit = 32 - Integer.numberOfLeadingZeros(x); // 获取 x 二进制位数的前导零个数if(bit > p) continue;ans += prefix[p - bit];ans %= MOD;}System.out.println(ans);}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}
}