题目描述
存在一个无限大小的集合(无重复元素)$S$,并且给定你 $n~ (1\le n \le 2\times10^5)$ 个数,且每个元素 $a_i ~(1 \leq a_i \leq 10^9)$ 。
并且定义这个集合的元素 $x$ 为至少符合以下一个条件:
- $x = a_i$ 对任意 $1 \leq i \le n$
- $x=2y+1 \land y \in S$
- $x = 4y \land y \in S$
请输出所有在集合 $S$ 中且满足 严格小于 $2^p$ 的元素数目。由于答案很大,请输出其对 $10^9 + 7$ 的结果。
题目分析
对于题目的数据范围这么大的条件,我们肯定需要考虑某种递推或者组合计数。
首先需要知道一个特性:
- 操作 $2$ 都是等价于在 $(x)_2$ 后面直接补一个 $1$
- 操作 $3$ 等价于在 $(x)_2$ 后面直接补 $00$
先特殊的考虑:考虑当 $n = 1 ~ \text{and} ~ a_1 = 1$ 时,此时有对于答案中的每一个 $x$ ,一定有且仅有一个 $k$ 使得 $2^k \le x \le 2^{k + 1}$ 成立。换言之,$k = \lfloor \log x \rfloor$ 。
比方说 $x = 13 = 1011_2 \rightarrow 2^k = 1000_2 \le x < 10000_2 = 2^k + 1 \rightarrow k = 3$
因此,我们定义 $f(x) = k$ ,因此通过上述两操作有 $f(2x + 1) = f(x) + 1$ ,$f(4x) = f(x) + 2$ 。考虑操作后的二进制位数。
因此这引导我们考虑动态规划的递推。
所以,我们定义 $dp_i$ 表示所有满足 $x \in S \land f(x) = i$ 条件的 $x$ 的数量。$i$ 表示所有的在二进制表示下的位数 $-1$.
初始状态:$dp_0 = 1$ 因为当 $f(x) = 1 \rightarrow 1 \le x < 10_2 = 2$ 有且仅有 $x = 1$ 符合条件,因此数量是 $1$。
状态转移:
在一般意义下
$$dp_i = dp_{i - 1} + dp_{i - 2}$$
表示的含义是 位数
是 $i$ 的数字的数量等于 位数
是 $i - 1$ 和 $i - 2$ 的数字的数量之和。
为什么是这样的转移呢?其实可以这样理解:每一个集合中的 $(x)_2$ ,为了方便表示,不妨设 $x = 1100101_2$,都只能从 $x’ = 110010_2$ 转移过来(执行第一种操作);而当 $x = 1100100_2$ 时,只能从 $x’ = 11001_2$ 转移过来(执行第二种操作)。因此,每一个集合中的元素一定跟上一个元素 有且仅有一条边 ,这就是一个很漂亮的拓朴图,所以可以 $dp$。再者,二进制表示下,长度为 $i$ 的数字,一定只能从二进制下长度为 $i - 1$ 和长度为 $i - 2$ 的数字转移。
还有一种相对于比较好理解的方法,但是看起来并不是非常的严谨。
以下的考虑都是从二进制位数的角度考虑。
当有 $0$ 位数的时候,此时只能从 $0$ 位数变过来(不操作)。
当只有 $1$ 位数的时候,此时只能从 $1$ 位数变过来(不操作)。
当有 $2$ 位数的时候,此时可以从 $1$ 位数变过来($1$ 位数末尾添上一个 $1$)。
当有 $3$ 位数的时候,此时可以从 $1$ 位数变过来(末尾添两个 $0$),也可以从 $2$ 位数变过来(末尾添一个 $1$ )
当有 $4$ 位数的时候,此时可以从 $2$ 位数变过来(末尾添两个 $0$),可以从 $3$ 位数变过来(末尾添一个 $1$).
当有 $n$ 位数的时候,此时可以从 $n - 2$ 位数变过来(末尾添两个 $0$),也可以从 $n - 1$ 位数变过来(末尾添一个 $1$).
因此这是个斐波那契转移。
结束状态:$ans = \sum _{i = 0} ^ {p - 1} dp_i$ ,因为最终需要保证 $x < 2^p \rightarrow \max f(x) = p - 1$
至此,我们完成了状态方程的推导。
但是,还没有结束,这个题更加关键的地方在于排除冗余状态的重复计算。举个例子,当有 $a_i = 1, a_j = 11_2$ ,那么所有 $a_j$ 能到达的状态 $a_i$ 一定能到达,因此我们称 $a_i$ 这种数为 useful number
,而称 $a_j$ 这种数为 useless number
。在计算的时候,我们只需要考虑从所有的 $a$ 中的 useful number
开始进行转移才能做到不重复的转移。
对于每个元素,最终至多仅有 $O(\log a_i)$ 个元素可能形成它,因此它至多只有 $O(\log a_i)$ 个父亲节点。并且我们可以知道它的父亲节点一定是 严格小于 它本身,因此我们可以先对 $a$ 排个序,使得对当前的 $a_i$ ,我们能判断比 $a_i$ 小的数是不是它的父亲。
所以我们可以通过 $O(n \log a_i)$ 的时间,预处理出来所有在 $a$ 中的 useful number
,具体来说,我们维护一个 unordered_set
,表示前的 useful number
,然后对当前的 $a_i$,我们对他不断进行题设操作的逆操作,因为每一步一定是唯一确定的,且不会同时发生,因此我们不需要考虑分杈分枝。
最终,保留在 set
中的元素就一定都是 useful number
,我们只需要从这些数字开始转移即可。
具体来说,我们可以如下判断:
- 假如末尾是 $1$ ,那么它一定只能从 $x >> 1$ 转移过来
- 假如末尾是 $00$ ,那么它一定只能从 $x >> 2$ 转移过来
- 否则末尾一定就是 $10$,此时他没法转移,直接 break 就可以了
然后在找父亲的时候维护一个变量 useless
表示是不是之前出现过的 useful number
, 如果之前已经出现过那就不要重复计算。
sort(all(a));
unordered_set <int> useful;
for (int i = 0; i < n; i ++) {
int x = a[i], useless = 0;
while(x) {
if(useful.count(x)) {
useless = 1;
break;
}
if(x & 1) {
x >>= 1;
} else if (x >> 1 & 1) {
break;
} else {
x >>= 2;
}
}
if (!useless) useful.insert(a[i]);
}
一些细节
在对于 $dp$ 方程初始化的时候,我们需要知道所有的 useful number
的位数,因此需要遍历一遍 set
然后对应的位置 +1
表示计入起始点。因此我们可以维护一个 cnt
数组,大小至多是 $32$ ,因为 $a_i \le 10^9$ 。
时间复杂度
在预处理 useful number
时,我们用了 $O(n \log a_i)$ 的时间,然后在状态转移的时候,用了 $O(p)$ 的时间,因此总的时间复杂度是 $O(n \log a_i + p)$
Code
不得不说一句 Jls 的取模板子真好用啊
IOS;
int n, p;
cin >> n >> p;
vector <int> a(n);
vector <Z> dp(p + 5);
vector <int> cnt(50);
for (int i = 0; i < n; i ++) cin >> a[i];
sort(all(a));
unordered_set <int> useful;
for (int i = 0; i < n; i ++) {
int x = a[i], useless = 0;
while(x) {
if(useful.count(x)) {
useless = 1;
break;
}
if(x & 1) x >>= 1;
else if (x >> 1 & 1) break;
else x >>= 2;
}
if (!useless) useful.insert(a[i]);
}
for (int x : useful) {
cnt[__lg(x)]++;
}
Z ans = 0;
for (int i = 0; i < p; i ++) {
if (i < min(p, 32)) dp[i] = Z(cnt[i]);
if (i) dp[i] += dp[i - 1];
if (i >= 2) dp[i] += dp[i - 2];
ans += dp[i];
}
cout << ans;
return 0;
%%%