acwing1875. 贝茜的报复（二进制枚举）

农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。
约翰给贝茜出了一道相当难的问题，导致她没能解决。
现在，她希望通过给约翰出一道有挑战性的难题来报复他。
贝茜给了约翰一个表达式 (B+E+S+S+I+E)(G+O+E+S)(M+O+O)(B+E+S+S+I+E)(G+O+E+S)(M+O+O)，其中包含七个变量 B,E,S,I,G,O,MB,E,S,I,G,O,M（OO 是变量，不是零）。
对于每个变量，她给约翰一个列表，表中包含该变量可采用的最多 2020 个整数值。
她要求约翰计算，共有多少种给变量赋值的方法可以使得表达式的计算结果为偶数。

输入格式

第一行包含一个整数 NN。
接下来 NN 行，每行包含一个变量和该变量的一个可能值。
每个变量至少出现 11 次，最多出现 2020 次。
同一变量不会重复列出同一可能值。

输出格式

输出可以使得表达式的计算结果是偶数的给变量赋值的方法总数。

数据范围

7≤N≤1407≤N≤140,
所有变量的可能取值范围 [−300,300][−300,300]
本题答案不会超出int范围。

输入样例：

10 B 2 E 5 S 7 I 10 O 16 M 19 B 3 G 1 I 9 M 2

输出样例：

6

样例解释

共有 66 种可能的赋值方式：
(B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244 = (2, 5, 7, 10, 1, 16, 2 ) -> 35,496 = (2, 5, 7, 9, 1, 16, 2 ) -> 34,510 = (3, 5, 7, 10, 1, 16, 2 ) -> 36,482 = (3, 5, 7, 9, 1, 16, 19) -> 53,244 = (3, 5, 7, 9, 1, 16, 2 ) -> 35,496
注意，(2, 5, 7, 10, 1, 16, 19) 和 (3, 5, 7, 9, 1, 16, 19)，虽然计算结果相同，但是赋值方式不同，所以要分别计数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
int n;
int main() {
    cin >> n;
    unordered_map<char,int> cnt[2];     //cnt[0]记录奇数个数,cnt[1]记录偶数个数
    while (n --) {
        char c;
        int x;
        cin >> c >> x;
        cnt[abs(x) % 2][c] ++;
    }
    int res = 0;
    char str[] = "BESIGOM";
    unordered_map<char,int> v;      //v存储每种方案里各字母是奇数还是偶数
    //二进制枚举所有方案,利用加减乘可在里面就mod2不会影响结果性质
    for (int i = 0; i < 1 << 7; ++i) {
        for (int j = 0; j < 7; ++j) 
            v[str[j]] = i >> j & 1;
        if ((v['B'] + v['I']) * (v['G'] + v['O'] + v['E'] + v['S']) * v['M'] % 2 == 0) {
            int sum = 1;
            for (int j = 0; j < 7; ++j) 
                sum *= cnt[i >> j & 1][str[j]];
            res += sum;
        } 
    }
    cout << res << endl;
    return 0;
}