题目
农夫约翰和奶牛贝茜喜欢在业余时间互相出数学题。
约翰给贝茜出了一道相当难的问题，导致她没能解决。
现在，她希望通过给约翰出一道有挑战性的难题来报复他。
贝茜给了约翰一个表达式 (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≤N≤140,
所有变量的可能取值范围 [?300,300]
输入样例：
10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2
输出样例：
6
样例解释
共有 6 种可能的赋值方式：
(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)，虽然计算结果相同，但是赋值方式不同，所以要分别计数。
解题思路
首先，题目中的式子为
(
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+S+I+E)(G+O+E+S)(M+O+O)
可以化简为
(
B
+
I
+
2
E
+
2
S
)
(
E
+
G
+
O
+
S
)
(
M
+
2
O
)
(B+I+2E+2S)(E+G+O+S)(M+2O)
(B+I+2E+2S)(E+G+O+S)(M+2O)
因为题目中要求结果为偶数即可
而偶数+偶数 = 偶数
奇数+偶数 = 奇数
所以每一项里的偶数对每一项的奇偶没有影响，即2E,2S,2O并不会影响最终结果所以式子可以化简为
M
(
B
+
I
)
(
E
+
G
+
O
+
S
)
M(B+I)(E+G+O+S)
M(B+I)(E+G+O+S)
且式子中 7 个变量均出现了，所以去掉其中的偶数项不会影响方案数
又因为偶数*偶数 = 偶数
奇数*偶数 = 偶数
所以只要这三项中有一项为偶数即可，其他两项中的数可以随意组合
设某变量为 0 时代表该变量为偶数，为 1 时代表该变量为奇数
那么当 M 为偶数时，即 M 的状态为 0 时，最后结果必为偶数，其他数的所有组合均为可行解
当 B 和 I 都为偶数或者都为奇数时，即两者状态相同，均为 0 或者均为 1 时，即两者异或等于 0 时，最后结果必为偶数，其他数的所有组合均为可行解
当 E,G,O,S 都为偶数，或者都为奇数，或者两奇两偶时，即奇数的个数为偶数个时，即四者状态异或为 0 时，最后结果必为偶数，其他数的所有组合均为可行解
每
一
个
可
行
解
的
方
案
数
=
∏
j
=
0
6
第
j
个
变
量
当
前
状
态
(
偶
数
/
奇
数
)
的
个
数
每一个可行解的方案数=\prod\limits_{j = 0}^6 第 j 个变量当前状态(偶数/奇数)的个数
每一个可行解的方案数=j=0∏6?第j个变量当前状态(偶数/奇数)的个数
总方案数就是将每一个方案数相加
Java代码
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0;
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
map.put('M', 6);
map.put('B', 5);
map.put('I', 4);
map.put('E', 3);
map.put('G', 2);
map.put('O', 1);
map.put('S', 0);
int[][] count = new int[7][2];
for(int i = 0; i < n; i++) {
char ch = sc.next().toCharArray()[0];
int x = sc.nextInt();
if(x % 2 == 0) count[map.get(ch)][0]++;
else count[map.get(ch)][1]++;
}
for(int i = 0; i < 1 << 7; i++) {
boolean m = (i >> 6 & 1) == 0;
boolean b_i = ((i >> 5 & 1) ^ (i >> 4 & 1)) == 0;
boolean e_g_o_s = ((i >> 3 & 1) ^ (i >> 2 & 1) ^ (i >> 1 & 1) ^ (i & 1)) == 0;
int temp = 1;
if(m || b_i || e_g_o_s) {
for(int j = 0; j < 7; j++) {
temp *= count[j][(i >> j) & 1];
}
sum += temp;
}
}
System.out.println(sum);
sc.close();
}
}
```
|