0%

1875.贝茜的报复

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
2
3
4
5
6
7
8
9
10
11
10
B 2
E 5
S 7
I 10
O 16
M 19
B 3
G 1
I 9
M 2

输出样例:

1
6

样例解释

共有 6 种可能的赋值方式:

1
2
3
4
5
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+I)(G+O+E+S)(M) ,同时把每个变量的取值降低为两种,一奇一偶,这样的话复杂度变为 $ O(2^7) $ 可以接受。

代码:

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
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
// char 奇 偶
unordered_map<char, pair<int, int>> mp;
int ans;
// (B+I)(G+O+E+S)(M)
unordered_map<char, int> tmp;
string s = "BIGOESM";
void dfs(int step, int cnt)
{
if (step == 7)
{
int sum = (tmp['B'] + tmp['I']) * (tmp['G'] + tmp['O'] + tmp['E'] + tmp['S']) * tmp['M'];
if (sum % 2 == 0)
ans += cnt;
return;
}
char ch = s[step];
tmp[ch] = 1;
dfs(step + 1, cnt * mp[ch].first);
tmp[ch] = 2;
dfs(step + 1, cnt * mp[ch].second);
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int tcase;
cin >> n;
char ch;
int x;
for (int i = 1; i <= n; i++)
{
cin >> ch >> x;
if (x & 1)
mp[ch].first++;
else
mp[ch].second++;
}
dfs(0, 1);
cout << ans << endl;
return 0;
}