Binääripuu

input/code.cpp: In function 'std::__cxx11::string add(std::__cxx11::string, std::__cxx11::string)':
input/code.cpp:30:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        if(i < a.length() && a[i] == '1') {
           ~~^~~~~~~~~~~~
input/code.cpp:33:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        if(i < b.length() && b[i] == '1') {
           ~~^~~~~~~~~~~~
input/code.cpp: In function 'std::__cxx11::string toBin(std::__cxx11::string)':
input/code.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.length(); i+=2) {
                    ~~^~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); ++i) {
                    ~~^~~~~~~~~~

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>


using namespace std;

typedef long long ll;
typedef pair<int, string> is;

vector<is> e;

const int C = 205;

string po[C][100]; //n*10^k in binary

string add(string a, string b) {
    //Add two binary strings together
    int m = max(a.length(), b.length());
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    
    string res = "";
    int plusOne = 0;
    for(int i = 0; i < m; ++i) {
       int A = 0;
       int B = 0;
       if(i < a.length() && a[i] == '1') {
           ++A;
       }
       if(i < b.length() && b[i] == '1') {
           ++B;
       }
       
       if(A+B+plusOne == 3) {
           plusOne = 1;
           res += "1";
       } else if (A+B+plusOne == 2) {
           plusOne = 1;
           res += "0";
       } else if (A+B+plusOne == 1) {
           plusOne = 0;
           res += "1";
       } else {
           res += "0";
       }
    }
    if(plusOne == 1) {
        res += "1";
    }
    reverse(res.begin(), res.end());
    return res;
}

void init() {
    po[0][1] = "1";
    for(int i = 1; i < C; ++i) {
        string a = po[i-1][1] + "000";
        string b = po[i-1][1] + "0";
        po[i][1] = add(a, b);
    }
    
    for(int i = 2; i < 100; ++i) {
        for(int j = 0; j < C; ++j) {
            po[j][i] = add(po[j][i-1], po[j][1]);
        }
    }
}

string toBin(string a) {
    reverse(a.begin(), a.end());
    if(a.size()%2 == 1) a+="0";
    string b = "";
    for(int i = 0; i < a.length(); i+=2) {
        int digit1 = (int) (a[i] - '0');
        int digit2 = (int) (a[i+1] - '0');
        int to = digit1 + 10*digit2;
        if(to == 0) continue;
        b = add(b, po[i][to]);
    }
    return b;
}

unordered_map<string, bool> ma[C][C];


const int M = 1e9 + 7;

ll exp(ll a, ll e) {
    if(e == 0) return 1;
    if(e%2 == 0) {
        ll c = exp(a, e/2);
        return (c*c)%M;
    }
    ll c = exp(a, e-1);
    return (a*c)%M;
}

ll powers[65]; //Powers of two

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

    init();
  //  string a = "124331232131521";
  //  a = toBin(a);
    for(int i = 1; i <= m; ++i) {
        string a;
        cin >> a;
        a = toBin(a);
    
    //    a = add(a, toBin("132411"));
        e.push_back({a.length(), a});

    }
    sort(e.begin(), e.end());
    
    vector<string> v;

    for(int i = 0; i < m; ++i) {
        string s = e[i].second;
 
        int ind = 0;
        if(s[1] == '1') {
            ind = 1;
        }
        bool fo = false;
        while(s.length() >= 1) {
        
            if(ma[s.length()][ind][s]) {
                fo = true;
                break;
            }
            s.pop_back();
        }
        if(fo) continue;
        v.push_back(e[i].second);
        ma[e[i].second.length()][ind][e[i].second] = true;
    }
    for(int i = 0; i <= n; ++i) {
        powers[i] = exp(2, i);
    }
    
    ll le = powers[n-2];
    ll ri = powers[n-2];
    
    for(int i = 0; i < v.size(); ++i) {
        
        if(v[i][1] == '1') {
            //Right
            ri -= powers[n - v[i].length()];
            ri %= M;
        } else {
            //Left
            le -= powers[n-v[i].length()];
            le %= M;
        }
    }
    
    
    ll ans = 2*le*ri;
    ans %= M;
    if(ans < 0) {
        ans += M;
    }
    
    cout << ans << "\n";
    
}

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: TIME LIMIT EXCEEDED

Test 56

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 57

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 58

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 59

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 60

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 61

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 62

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 63

Group: 3

Verdict: ACCEPTED

Test 64

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 65

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 66

Group: 3

Verdict: TIME LIMIT EXCEEDED

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