题意

给定一个数组，我们可以通过2种方式扩张这个数组：

选取数组中的一个数，令其为x，将2*x+1的结果也加入到数组中
选取数组中的一个数，令其为x，将4*x的结果也加入到数组中

给定一个p，问通过扩张后数组小于2^p的元素个数有几个，结果对1e9+7取模。原数组大小和p最大为1e5。

思路

我们首先考虑原数组仅有一个元素时，我们应当如何计算结果。考虑到p的范围达到了10^5次，2^p暗示了我们可能可以从二进制的方向考虑这个问题。考虑我们拥有的两种操作：

2*x+1：如果我们将一个数字看作一个01字符串，那么2*x+1就可以看作是在01串的末尾增加一个’1’
4*x:同样，看作一个01字符串后，4*x可以看作在01串的末尾增加一个’00’

基于这个观察结果，我们能够发现长度为i，满足被生成条件的01串，能够从i-1长度满足条件的01串末尾加’1’及从i-2长度满足条件的01串末尾添加’00’转移得到。即存在转移方程

$dp[i] = dp[i-1]+dp[i-2]$

同时我们注意到，当仅有一个元素时，两种操作产生的数字不会产生重叠！1操作仅仅会为数字添加1，而2操作仅仅会为数字添加0.所以两种操作永远不会在起始数组仅有一个元素时，产生重叠的元素，进而在转移方程中，我们不用考虑重复的情况。

在解决了数组仅有一个元素后，我们需要注意，对于多个元素的起始数组，我们需要考虑去重的问题。什么样的两个01串a,b会导致重复元素c？根据操作的特性，我们能发现，a和b一定都是c的前缀。进一步，根据操作的特性，我们也能发现a，b中较长的串，应当是由较短的串通过操作生成的！这里我们还能发现，如果从较短的串找较长的串，必须要dfs遍历所有可能，但是如果从较长的串找较短的串，那么就有：

末尾为1时，将该数字除2，因为1只可能从操作1得到，所以反向就是除2
末尾为2（01串为’10’)退出循环，因为10是不可能通过操作得到的）
末尾为00，将该数字除4，对应操作2的反向操作

通过去除重复生成串中较长的串，我们就能得到操作后不会重叠的数组。这时使用dp转移方程就能得到答案。

思考

数据范围为2的指数次幂，可以考虑往bitset方向考虑
从小数据往大数据思考
操作带*2, *4时，要对二进制方向有敏感性

代码

#include <bits/stdc++.h>
#define ms(a, val) memset(a, val, sizeof a);
#define ll long long
#define ull unsigned long long
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(), (x).end()

using namespace std;
template<class T> void read(T& x) {
    cin>>x;
}

const int MAXN = 200005;
int dp[MAXN], a[MAXN];
const int MOD = 1e9+7;

int main(){
#ifndef ONLINE_JUDGE
    freopen("./input.txt","r",stdin);
    freopen("./output.txt","w",stdout);
#endif // ONLINE_JUDGE
    int n, p;
    while(~scanf("%d%d", &n,&p)) {
        ms(dp, 0);
        for (int i = 0;i < n;i++) {
            read(a[i]);
        }
        set<int> useful;
        sort(a, a+n);
        for (int i = 0;i < n;i++) {
            int flag = true;
            int x = a[i];
            while(x) {
                if(useful.count(x)) {
                    flag = false;
                }
                if (x&1) {
                    x>>=1;
                } else if(x&2) {
                    break;
                } else {
                    x>>=2;
                }
            }
            if(flag) {
                useful.insert(a[i]);
            }
        }
        for(set<int>::iterator it = useful.begin();it!=useful.end();it++) {
            double x = *it;
            dp[(int)log2(x)]++;
        }
        int ans = 0;
        for(int i=0;i<p;i++) {
            if(i>=1) {
                dp[i] = (dp[i]+dp[i-1])%MOD;
            }
            if(i>=2) {
                dp[i] = (dp[i]+dp[i-2])%MOD;
            }
            ans = (ans+dp[i])%MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}

参考

Codeforces Round #772 Editor