[数据结构与算法]D. Infinite Set（线性dp）

Problem - D - Codeforces

D. Infinite Set

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array?aa?consisting of?nn?distinct?positive integers.

Let's consider an infinite integer set?SS?which contains all integers?xx?that satisfy at least one of the following conditions:

1. x=aix=ai?for some?1≤i≤n1≤i≤n.
2. x=2y+1x=2y+1?and?yy?is in?SS.
3. x=4yx=4y?and?yy?is in?SS.

For example, if?a=[1,2]a=[1,2]?then the?1010?smallest elements in?SS?will be?{1,2,3,4,5,7,8,9,11,12}{1,2,3,4,5,7,8,9,11,12}.

Find the number of elements in?SS?that are strictly smaller than?2p2p. Since this number may be too large, print it modulo?109+7109+7.

Input

The first line contains two integers?nn?and?pp?(1≤n,p≤2?105)(1≤n,p≤2?105).

The second line contains?nn?integers?a1,a2,…,ana1,a2,…,an?(1≤ai≤109)(1≤ai≤109).

It is guaranteed that all the numbers in?aa?are distinct.

Output

Print a single integer, the number of elements in?SS?that are strictly smaller than?2p2p. Remember to print it modulo?109+7109+7.

Examples

input

Copy

2 4
6 1

output

Copy

9

input

Copy

4 7
20 39 5 200

output

Copy

14

input

Copy

2 200000
48763 1000000000

output

Copy

448201910

Note

In the first example, the elements smaller than?2424?are?{1,3,4,6,7,9,12,13,15}{1,3,4,6,7,9,12,13,15}.

In the second example, the elements smaller than?2727?are?{5,11,20,23,39,41,44,47,79,80,83,89,92,95}{5,11,20,23,39,41,44,47,79,80,83,89,92,95}.

题意：在一个无限集合S中，如果在数组a出现，那么在S中也出现，还要满足三个条件之一。

（昨晚看了好久都没看懂题）。

解题思路：

我们可以确定任何一个数都只有一种情况变换得来，如果数组a中某些数可以由其中某个数变换的来就可以去掉。然后我们可以试着从后面开始推，小于2^p次方的话，在2^p-1只能得到一个数他本身，2^p-2次方可以得到两个。。。。。然后发现居然有递推关系，就可以打个表，然后再看当前数是最高位，从该位开始有多少个。

递推方程：dp[i] = dp[i + 1] + dp[i + 2] + 1

这个数可以变成2^i+1次方加一， 也可以变成2^i+2次方，还要加上他本身。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <unordered_map>
#include <vector>
#include <queue>
#include <functional>
#include <cstdio>

using namespace std;

#define ll long long
#define PII pair<int, int>

const int N = 2e5+100, mod = 1e9+7;
ll a[N], dp[N];

int main() {
    int n, p;
    cin >> n >> p;

    unordered_map<ll, bool>mp;
    for (int i = 1; i <= n; i ++) cin >> a[i], mp[a[i]] = true;

    vector<ll>all(1, 0);
    for (int i = 1; i <= n; i ++){
        int tmp = a[i];
        bool flag = true;
        while (tmp){
            if (tmp & 1) tmp >>= 1;
            else{
                if (tmp & (1 << 1))  break;
                tmp >>= 2;
            }
            if (mp[tmp]) flag = false;
        }
        if (flag) all.push_back(a[i]);
    }
    dp[p - 1] = 1;
    if (p - 2 >= 0) dp[p - 2] = 2;
    for (int i = p - 3; i >= 0; i --){
        dp[i] = (dp[i + 1] + dp[i + 2] + 1)  % mod;
        //printf("---->dp[%d] = %d\n", i, dp[i]);
    }

    ll ans = 0;
    for (int i = 1; i < all.size(); i ++){
        int len = 0;
        while (all[i]){
            all[i] >>= 1;
            len++;
        }
        ans = (ans + dp[len - 1]) % mod;
    }
    cout << ans << endl;
    return 0;
}