cf1635D

题目大意

给定初始有\(n\)个正整数\(a_i(1\le n \le 2 * 10^5,1 \le a_i \le 10^9)\)集合\(S\)。 而满足下列条件的数\(y\),也会被添加进这个集合: * \(y = 2 * x + 1且x = a_i\) * \(y = 4 * x,且x = a_i\)

问，这个集合最终不超过\(2^p(1 \le p \le 2 * 10^5)\)的数的个数是多少。 题目链接 ## 思路

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

直接设\(dp_i\)表示\(i\)以内的数有多少个,那么我们可以轻松得出状态转移方程，但是，显然是开不下的。

我们注意到题目要求不超过\(2^p\),所以我们不妨用二进制来表示状态。

\(f_i\)表示有\(i\)位二进制位数，其以内的数有多少个。比如\(f_4\)就表示集合中小于等于\((1111)_{2}\) 且大于 \((1000)_{2}\)的数个数有多少(这么做可以防止重复计算)。

题目中的两种操作在二进制下就是这种操作: * \(x = x << 1 | 1\) * \(x = x << 2\)

我们来写一下状态转移方程\(f_i\): * 通过\(x = x << 1|1\)操作,所有\(f_{i - 1}\)中的数都可以转移过来 * 通过\(x = x << 2\)操作，所有\(f_{i - 2}\)中的数都可以转移过来

故，\(f_i = f_{i - 1} + f_{i - 2}\)

只有一个的情况我们已经表示出来了，那么假如初始的时候有多个数呢？ 假如一个数\(x\)可以被另一个数\(y\)产生出来，那么我们就不再需要\(x\)了。

那么具体怎么做呢？ * 我们先判断\(x\)是否包含在\(set\)中 * 如果二进制下\(x\)的末尾是\(1\),那么它可能由\[x = x << 1 | 1\]操作产生,所以我们令\(x >>= 1\) * 如果二进制下\(x\)的末尾是\(00\),那么它可能由\(x = x << 2\)操作产生,所以我们令\(x >>= 2\) * 如果\(x\)的后两位为\(11\),那么就无法继续下去了，结束这种操作。 * 结束循环后，如果\(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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/02/24/cf1635D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！