【Codeforces】1635D Infinite Set题解

题目大意

给定初始有 $n$ 个正整数 $a_i$（$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$）的集合 $S$。

满足下列条件的数 $y$ 也会被添加进集合：

• $y = 2 \cdot x + 1$，且 $x \in S$
• $y = 4 \cdot x$，且 $x \in S$

问这个集合最终不超过 $2^p$（$1 \le p \le 2 \times 10^5$）的数有多少个？

题目链接

思路

我们先假设初始集合中只有 $1$。那么 $3, 4$ 也会被添加进来，紧接着 $12, 16, 7, 9$ 也会被添加进来。多试几个数我们会发现，不同的操作产生的数不会产生重合。

设 $dp_i$ 为二进制位数为 $i$ 以内的数有多少个，我们可以轻松得出状态转移方程，但是用十进制数来表示显然是开不下的。

我们注意到题目要求不超过 $2^p$，所以我们不妨用二进制位数来表示状态。

$f_i$ 表示有 $i$ 位二进制位数时，集合中数的个数。比如 $f_4$ 就表示集合中二进制位数不超过 $4$（即 $\le (1111)_2$）的数的个数。

题目中的两种操作在二进制下就是：

• $x = (x \mathbin{<<} 1) \mid 1$（末尾加 $1$）
• $x = x \mathbin{<<} 2$（末尾加 $00$）

我们来写一下状态转移方程 $f_i$：

• 通过 $x = (x \mathbin{<<} 1) \mid 1$ 操作，所有 $f_{i-1}$ 中的数都能产生一个 $i$ 位的数。
• 通过 $x = x \mathbin{<<} 2$ 操作，所有 $f_{i-2}$ 中的数都能产生一个 $i$ 位的数。

故：

$$f_i = f_{i-1} + f_{i-2}$$

只有一个初始数的情况我们已经表示出来了，那么假如初始有多个数呢？

假如一个数 $x$ 可以被另一个数 $y$ 产生出来，那么我们就不再需要 $x$ 了。具体做法：

• 我们先判断 $x$ 是否包含在 set 中。
• 如果二进制下 $x$ 的末尾是 $1$，那么它可能由 $x = (x \mathbin{<<} 1) \mid 1$ 操作产生，令 $x \mathbin{>>=} 1$。
• 如果二进制下 $x$ 的末尾是 $00$，那么它可能由 $x = x \mathbin{<<} 2$ 操作产生，令 $x \mathbin{>>=} 2$。
• 如果 $x$ 的后两位为 $10$，那么就无法继续下去了，结束循环。
• 结束循环后，如果 $x$ 无法被 set 中的数表示，那就把 $x$ 加入 set 中。

代码

#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

const int maxN = 2e5 + 7;
const long long Mod = 1e9 + 7;
int n, p, a[maxN], cnt[35];
long long f[maxN];

inline int calc(int x)
{
    int cnt = 0;
    while(x) {
        cnt++;
        x >>= 1;
    }
    return cnt;
}

int main()
{
    scanf("%d%d", &n, &p);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    set<int> num;
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i) {
        if(calc(a[i]) > p)
            continue;
        bool hav = false;
        int x = a[i];
        while(x) {
            if(num.count(x)) {
                hav = true;
                break;
            }
            if(x & 1)
                x >>= 1;
            else if(x & 3)
                break;
            else
                x >>= 2;
        }
        if(!hav)
            num.insert(a[i]);
    }
    for(auto i : num) 
        cnt[calc(i)]++;
    long long ans = 0;
    for(int i = 1; i <= 33; ++i)
        f[i] = cnt[i];
    f[2] += f[1];
    ans = (ans + f[2] + f[1]) % Mod;
    for(int i = 3; i <= p; ++i) {
        f[i] = (f[i] + f[i - 1] + f[i - 2]) % Mod;
        ans = (ans + f[i]) % Mod;
    }
    printf("%lld\n", ans);
    return 0;
}