1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <set>
#include <vector>

using namespace std;

set<int> lT[1000001];
set<int> lF[1000001];
string text;
set<int> b;

void extractOne(int n, int from, int to) {
    bool negate = false;
    if (text[from] == '~') {
        negate = true;
        from++;
    }
    from++;

    int k = to;
    while (text[k] == ' ') k--;
    int p = 1;
    int number = 0;
    while (k >= from) {
        number += p * (text[k] - '0');
        p *= 10;
        k--;
    }
    if (negate) {
        lF[number].insert(n);
    } else {
        lT[number].insert(n);
    }
    b.insert(number);
}

void extractV(int nrK, int from, int to) {
    int i = from;
    while (i <= to) {
        int start = i;
        while (i <= to && text[i] != 'v') {
            i++;
        }
        extractOne(nrK, start, i - 1);
        i = i + 2;
    }
}

int main() {
    int n;
    cin >> n;
    cin.get();
    getline(cin, text);

    int nrK = 1;
    int pos = 0;

    while (pos < text.size()) {
        int start = pos;
        while (text[pos] != ')') {
            pos++;
        }
        if (nrK == 1) {
            extractV(nrK, start + 1, pos - 1);
        } else {
            extractV(nrK, start + 4, pos - 1);
        }
        pos++;
        nrK++;
    }

    /*
    for (set<int>::iterator it = b.begin(); it != b.end(); it++) {
        cout << "Variable number: " << *it << ". " << endl;
        cout << "Without negation in: ";
        for (set<int>::iterator itt = lT[*it].begin(); itt != lT[*it].end(); itt++) {
            cout << *itt << " ";
        }
        cout << endl << "With negation in: ";
        for (set<int>::iterator itt = lF[*it].begin(); itt != lF[*it].end(); itt++) {
            cout << *itt << " ";
        }
        cout << endl << endl;
    }
    */
    
    int count = 0;

    for (long long i = 0; i < (1 << b.size()); i++) {
        set <int> OK;
        int p = 1;
        int z = 1;
        while(p < (1 << b.size())) {
            if((p & i) != 0) {
                OK.insert(lT[z].begin(), lT[z].end());
            } else {
                OK.insert(lF[z].begin(), lF[z].end());
            }
            p *= 2;
            z++;
        }

        if(OK.size() == nrK - 1) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}