A - Two Choices

题意

$0$ か $1$ で答える問題 $M$ 問からなるテストがあり、これに $N$ 人の生徒が取り組みました。$N$ 個の長さ $M$ の文字列 $S_1,S_2,\ldots,S_N$ が与えられます。$S_i$ の $k$ 文字目は $0$ と $1$ のいずれかであり、 $i$ 番目の生徒の $k$ 問目に対する解答を示しています。各生徒の各問題に対する解答は判明していますが、各問題の正解が $0$ と $1$ のどちらであるかはまだ判明していません。 $1\le i<j\le N$ を満たす組 $(i,j)$ であって、生徒 $i$ と生徒 $j$ の正解した問題の数が等しい可能性がないようなものはいくつあるか求めてください。

解析

$i$ 与 $j$ 不可能答对同样多的题，当且仅当 $S_i$ 与 $S_j$ 的异或和的 $\text{popcount}$ 为奇数。

由于 $\operatorname{popcount}(S_i\oplus S_j)=\operatorname{popcount}(S_i)+\operatorname{popcount}(S_j)-2\operatorname{popcount}(S_i\& S_j)$，则 $\operatorname{popcount}({S_i\oplus S_j})$ 的 parity 与 $\operatorname{popcount}({S_i})+\operatorname{popcount}({S_j})$ 的 parity 相同，只需要分别记录 $\text{popcount}$ 为奇、偶的 $S$ 的个数，相乘即可得到答案。

实现

#include <bits/stdc++.h>

int main(){
    int a = 0, b = 0;
    int n, m;
    std::scanf("%d%d", &n, &m);
    while(n--){
        bool flag = false;
        static char s[29];
        std::scanf("%s", s);
        for(int i = 0; i < m; ++i)
            if(s[i] == '0')
                flag ^= 1;
        if(flag) ++a;
        else ++b;
    }
    std::printf("%lld\n", (long long int)a * b);
}

来源

AtCoder Regular Contest 115 A - Two Choices

评论