1875. 贝茜的报复
题目描述:
农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。
约翰给贝茜出了一道相当难的问题,导致她没能解决。
现在,她希望通过给约翰出一道有挑战性的难题来报复他。
贝茜给了约翰一个表达式 (B+E+S+S+I+E)(G+O+E+S)(M+O+O),其中包含七个变量 B,E,S,I,G,O,M(O 是变量,不是零)。
对于每个变量,她给约翰一个列表,表中包含该变量可采用的最多 20 个整数值。
她要求约翰计算,共有多少种给变量赋值的方法可以使得表达式的计算结果为偶数。
输入格式
第一行包含一个整数 N。
接下来 N 行,每行包含一个变量和该变量的一个可能值。
每个变量至少出现 1 次,最多出现 20 次。
同一变量不会重复列出同一可能值。
输出格式
输出可以使得表达式的计算结果是偶数的给变量赋值的方法总数。
数据范围
$ 7 \le N \le 140, $
所有变量的可能取值范围 $ [−300,300] $
本题答案不会超出int
范围。
输入样例:
1 | 10 |
输出样例:
1 | 6 |
样例解释
共有 6 种可能的赋值方式:
1 | (B,E,S,I,G,O,M) = (2, 5, 7, 10, 1, 16, 19) -> 53,244 |
注意,(2, 5, 7, 10, 1, 16, 19)
和 (3, 5, 7, 9, 1, 16, 19)
,虽然计算结果相同,但是赋值方式不同,所以要分别计数。
题解:
保证答案是偶数,其中三项中必要有一项是偶数。
注意观察,其中第一项和第三项中出现二倍的某些变量,一定是偶数,又因为偶数加偶数为偶数,偶数加偶数为奇数。不改变原数的奇偶性,因此可以直接忽略掉。那么公式变成了 (B+I)(G+O+E+S)(M) ,同时把每个变量的取值降低为两种,一奇一偶,这样的话复杂度变为 $ O(2^7) $ 可以接受。
代码:
1 | using namespace std; |