题目链接
题解：这个题求得是不小于2 ^ p 的情况下集合中的数的数量。在做这个题之前，我们首先要知道的是，将一个数化为二进制的话，每乘一个2就会往整体向前移动一位，整体加1位；乘以4的话也会整体向前移动两位，整体加2位。对于本题而言，x * 4满足上述条件，x * 2+1的话虽然大于 x * 2 但是两者的位数是一样的，而本题要求的是严格小于2 ^ p所以必须比2 ^ p 小一位所以对他的大小不必知道，所以也是满足以上所述。所以我们可以求得当前的数比2 ^ p小几位，然后再减1再求这样的数有几个，我们可以设i位的数有f[i]个，哪么就本题来说，f[i]=f[i-1]+f[i-2]即可以由i-1位的数乘2 或是 i-2位的数乘4，初始的话就是f[0]=1,f[1]=1。这样我们发现，这个是一个斐波那契数列。 此题要注意的是一定要去重，假设数组中出现 2 8 哪么只需要让2不断进行操作就可以了，8的话会和2重复。
下面是在cf上找的一个代码，思路是一样的：
#include <bits/stdc++.h>
using namespace std;
#define N 200200
const int mod = 1e9 + 7;
int n, p, a[N], f[N], g[N];
map <int, int> mp;
int main()
{
scanf("%d %d", &n, &p);for (int i = 1; i <= n; i ++) scanf("%d", &a[i]), mp[a[i]] = i;f[0] = f[1] = 1;for (int i = 2; i <= p; i ++) f[i] = (f[i-1] + f[i-2]) % mod;//i位的数可以由i-1位乘2，也可以由i-2位乘4g[0] = f[0]; //这里是先把自己算上，然后再算其他的for (int i = 1; i <= p; i ++) g[i] = (g[i-1] + f[i]) % mod;//相当一个前缀和int ans = 0;//x=2*y 与 x=2*y+1对位数没有影响所以直接按照2*y即可for (int i = 1; i <= n; i ++){
bool bad = false;int x = a[i];while (x > 1){
if (x & 1) x >>= 1;else if (x % 4 == 0) x >>= 2;else break;if (mp[x]){
bad = true;break;}}//这里的作用就是去重if (bad) continue;//相当于p+1-(32-x)-1=p-1-(31-x);int k = p - (32 - __builtin_clz(a[i]));//表示比p少的位数，注意这个函数一定要在int 范围内使用if (k < 0) continue;ans = (ans + g[k]) % mod;}printf("%d\n", ans);return 0;
}注：g[i]的作用相当于 f[0]+f[1]+f[2]+……即一个前缀和的作用，题中的那个函数的意思是32-a[i]的位数，32 - __builtin_clz(a[i])表示a[i]的位数。
再者就是这个f[0]和f[1]其实带入到具体的语境中
假设差1位到p-1位，哪么只有1个数就是乘2 那么g[1]=f[1]+f[0] 这里f[0]就是理解为本身，因为a[i]本身这个数能够满足情况的话也要算的。