Table of contents: Algorithm Diary

1875. Bessie’s Revenge

Topic describes

Farmer John and Bessie the cow like to solve maths problems with each other in their spare time.

John had given Bessie such a difficult problem that she could not solve it.

Now she hopes to get back at John by giving him a challenging problem.

Bessie gave John an expression (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), Contains seven variable B, E, S, I, G, O, MB, E, S, I, G, O, MB, E, S, I, G, O, M.

For each variable, she gives John a list of the maximum 202,020 integer values that can be taken for that variable.

She asked John to calculate how many ways to assign a value to a variable that would result in an even expression.

Input format

The first line contains an integer NNN.

NNN lines follow, each containing a variable and a possible value for that variable.

Each variable occurs at least 111 times and at most 202,020 times.

The same variable does not list the same possible values twice.

The output format

Output the total number of ways to assign a variable such that the expression evaluates to an even number.

Data range


  • 7 Or less N Or less 140 7 N acuities were 140 or less
  • Possible values of all variables [−300,300][−300,300][−300,300]
  • The answer to this question is no moreintRange.

Algorithm ideas

And they want to figure out how many different ways to assign a variable to an expression (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) calculations for even, can consider violence calculation every possible solution. There are 777 variables, and each variable can take a maximum of 202,020 integers, so there are 20720^7207 possible scenarios. Consider optimization.

Note only statistics (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) calculation result is even, It’s the same thing as dividing by the remainder of 222 is equal to 000. For multiplication, addition and subtraction, the mod operation has the distributive law, that is, the value of each variable is mod 222 directly, there are only 0,10,10,1, corresponding to all possible cases reduced to 272^727, after such treatment can be solved by violence.

777 variables are represented by 777 binary bits. Enumerate each combination of even results, and calculate the combination of legal assignment methods according to the principle of multiplication. Since the sum of two identical numbers must be even, this property can be used to simplify the judgment condition.

AC code

#include<iostream>
#include<map>
using namespace std;
map<char.int> cnt[2];
int n;
int main(a) {
    cin>>n;
    for(int i = 0; i < n; ++i) {
        char c;
        int x;
        cin>>c>>x;
        cnt[abs(x % 2)][c]++;
    }
    char str[] = "BESIGOM";
    int res = 0;
    // Enumerate each possibility
    for(int i = 0; i < 1 << 7; ++i) {
        map<char.int> v;
        // Fetch each digit
        for(int j = 0; j < 7; ++j) {
            v[str[j]] = i >> j & 1;
        }
        // Check the number of valid schemes. If true, the current enumerated state is valid
        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[v[str[j]]][str[j]];
            }
            res += sum;
        }
    }
    cout<<res<<endl;
    return 0;
}
Copy the code