暑假第一周

D. Infinite Set（二进制+dp）

关键是看成二进制，乘以4相当于补两个0，乘2加1相当于补一个1

dpi表示二进制表示长度为i的方案数，那么有dpi = dpi-1+dpi-2

那么考虑怎么处理已经有的数

首先要去掉一些重复的数，也就是一个数如果能被另一个数生成，就去掉

这个很好处理，就暴力枚举当前数可能由哪些数生成，然后用map看是否是已经有的数即可

那么用gi表示原本就已经有的数长度为i的有多少个

那么dpi = dpi + dpi-1 + gi

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int a[N], dp[N], g[N], n, p;
unordered_map<int, int> mp;

int len(int x)
{
    int res = 0;
    while(x) res++, x >>= 1;
    return res;
}

bool check(int x)
{
    while(x)
    {
        if(x % 4 == 0)
        {
            x /= 4;
            if(mp[x]) return false;
        }
        else if((x - 1) % 2 == 0)
        {
            x = (x - 1) / 2;
            if(mp[x]) return false;
        }
        else break;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &p);
    _for(i, 1, n) scanf("%d", &a[i]), mp[a[i]] = 1;

    _for(i, 1, n)
        if(check(a[i]))
            g[len(a[i])]++;

    dp[1] = g[1];
    _for(i, 2, p)
        dp[i] = (dp[i - 1] + dp[i - 2] + g[i]) % mod;

    int ans = 0;
    _for(i, 1, p) ans = (ans + dp[i]) % mod;
    printf("%d\n", ans); 
    
	return 0;
}