摘要
Title: 1875. 贝茜的报复
Tag: 二进制枚举、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

1875. 贝茜的报复

题意

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

我们只需要知道结果是否是偶数即可，所以直接可以将%2带入等式

$\begin{aligned} &(B+E+S+S+I+E)(G+O+E+S)(M+O+O)\%2 \\ &= (B+I)(G+O+E+S)(M)\%2 \\ &= (B\%2+I\%2)(G\%2+O\%2+E\%2+S\%2)(M\%2) \hspace{50cm} \end{aligned}$

得出来结论，我们只需要判断每一位是否为奇偶即可，将奇偶结果带入题目的算式即可

问题转化为了，枚举所有方案的题目（尤其是每一个元素只有两个选择）
- DFS $O(2^n)$ 代码长
- 二进制枚举 $O(n * 2^n)$ 代码短

代码

1126ms

'''
Author: NEFU AB-IN
Date: 2022-01-24 19:26:58
FilePath: \ACM\Acwing\1875.py
LastEditTime: 2022-01-25 00:09:06
'''
from collections import Counter, defaultdict

d = [Counter(), Counter()] #每个元素的奇偶个数，分两个字典来装

if __name__ == "__main__":
    n = int(input())
    for _ in range(n):
        s, x = input().split()
        d[int(x) % 2][s] += 1
    res = 0
    str = 'BESIGOM'

    v = defaultdict(int)
    for i in range(1 << 7):
        for j in range(7):
            v[str[j]] = i >> j & 1
        # 判断是否为偶数
        if ((v['B'] + v['I']) * (v['G'] + v['O'] + v['E'] + v['S']) * v['M'] %
                2 == 0):
            sum = 1
            for j in range(7):
                sum *= d[i >> j & 1][str[j]]
            res += sum
    print(res)

1875. 贝茜的报复

题意

思路

代码