Binary tree

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <string>


using namespace std;

typedef long long LL;

const LL MAX = 100005;
const LL MOD = (1000 * 1000 * 1000) + 7;

LL n, k, l=1, r=1;
LL pow2[65] = {}, forbid[MAX] = {};

LL lvl(LL tar)
{
    LL ans = 1;
    while(tar != 1)
    {
        tar/=2;
        ans++;
    }
    return ans;
}

LL num_Leaf(LL tar)
{
    LL depth = n-lvl(tar);
    return pow2[depth];
}

bool b_Search(LL num, LL tar)
{
    bool found = false;
    LL lo = 0;
    LL hi = num-1;
    while(lo <= hi)
    {
        LL mid = lo + (hi - lo) / 2;
        if(forbid[mid] == tar)
        {
            found = true;
            break;
        }else if(forbid[mid] < tar)lo = mid+1;
        else hi = mid-1;
    }
    return found;
}

bool oLap(LL tar)
{
    bool boo = false;
    LL y = forbid[tar];
    while(!boo && y >= 1)
    {
        if(b_Search(tar, y))
        {
            boo = true;
            break;
        }
        y/=2;
    }
    return boo;
}

LL find_Type(LL tar)
{
    if(tar == 1)return 1;
    else
    {
        while(tar >= 4)tar /= 2;
        return tar;
    }
}

int main(void)
{
    cin >> n >> k;

    pow2[0] = 1;
    for(LL i0 = 1; i0 < 65; i0++)pow2[i0] = (pow2[i0-1] * 2) % MOD;
    for(LL i0 = 2; i0 < n; i0++)
    {
        l*=2;
        l%=MOD;
    }
    r = l;

    for(LL i0 = 0; i0 < k; i0++)cin >> forbid[i0];
    sort(forbid, forbid+k);


    for(LL i0 = 0; i0 < k; i0++)
    {
        LL x = forbid[i0];
        if(i0 == 0 || !oLap(i0))
        {
            if(find_Type(x) == 2)
            {
                l -= num_Leaf(x);
            }else r -= num_Leaf(x);
        }
        //cout << l << " " << r << endl;
    }
    cout << (l*r*2)%MOD << endl;
    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 1

Verdict: ACCEPTED

Test 19

Group: 1

Verdict: ACCEPTED

Test 20

Group: 1

Verdict: ACCEPTED

Test 21

Group: 1

Verdict: ACCEPTED

Test 22

Group: 1

Verdict: ACCEPTED

Test 23

Group: 1

Verdict: ACCEPTED

Test 24

Group: 1

Verdict: ACCEPTED

Test 25

Group: 1

Verdict: ACCEPTED

Test 26

Group: 1

Verdict: ACCEPTED

Test 27

Group: 1

Verdict: ACCEPTED

Test 28

Group: 1

Verdict: ACCEPTED

Test 29

Group: 1

Verdict: ACCEPTED

Test 30

Group: 1

Verdict: ACCEPTED

Test 31

Group: 1

Verdict: ACCEPTED

Test 32

Group: 1

Verdict: ACCEPTED

Test 33

Group: 1

Verdict: ACCEPTED

Test 34

Group: 1

Verdict: ACCEPTED

Test 35

Group: 1

Verdict: ACCEPTED

Test 36

Group: 2

Verdict: ACCEPTED

Test 37

Group: 2

Verdict: ACCEPTED

Test 38

Group: 2

Verdict: ACCEPTED

Test 39

Group: 2

Verdict: ACCEPTED

Test 40

Group: 2

Verdict: ACCEPTED

Test 41

Group: 2

Verdict: ACCEPTED

Test 42

Group: 2

Verdict: ACCEPTED

Test 43

Group: 2

Verdict: ACCEPTED

Test 44

Group: 2

Verdict: ACCEPTED

Test 45

Group: 2

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED

Test 55

Group: 3

Verdict: ACCEPTED

Test 56

Group: 3

Verdict: ACCEPTED

Test 57

Group: 3

Verdict: ACCEPTED

Test 58

Group: 3

Verdict: ACCEPTED

Test 59

Group: 3

Verdict: ACCEPTED

Test 60

Group: 3

Verdict: ACCEPTED

Test 61

Group: 3

Verdict: ACCEPTED

Test 62

Group: 3

Verdict: ACCEPTED

Test 63

Group: 3

Verdict: ACCEPTED

Test 64

Group: 3

Verdict: ACCEPTED

Test 65

Group: 3

Verdict: ACCEPTED

Test 66

Group: 3

Verdict: ACCEPTED

Test 67

Group: 3

Verdict: ACCEPTED

Test 68

Group: 3

Verdict: ACCEPTED

Test 69

Group: 3

Verdict: ACCEPTED

Test 70

Group: 3

Verdict: ACCEPTED

Test 71

Group: 3

Verdict: ACCEPTED

Test 72

Group: 3

Verdict: ACCEPTED

Test 73

Group: 3

Verdict: ACCEPTED

Test 74

Group: 3

Verdict: ACCEPTED

Test 75

Group: 3

Verdict: ACCEPTED

Test 76

Group: 3

Verdict: ACCEPTED

Test 77

Group: 3

Verdict: ACCEPTED