The first week of summer vacation

D. Infinite Set（ Binary system +dp）

The key is to look at binary , multiply 4 Equivalent to two 0, ride 2 Add 1 It's equivalent to adding one 1

dpi Indicates that the binary indicates that the length is i Number of alternatives , So there are dpi = dpi-1+dpi-2

Then consider how to deal with the existing numbers

First, remove some duplicate numbers , That is, if one number can be generated by another number , Just remove

This is very easy to handle , Enumerate which numbers the current number may be generated by , And then use map See if it's the number you already have

Then use gi It means that the length of the existing number is i How many

that 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;
}