# APCS 20190615 P3 卡通團隊
###### tags: `APCS`

## 題目大意
總共有 $m$ 個卡通人物，每個卡通人物以一個字母表示，
有 $n$ 個團隊，每一個團隊以一個字串表示，
當字串中含有某個英文字母時，表示這個團隊含有這個成員，
（字串中可能有重複的字母，重複幾次或沒有重複都沒有差別）
若兩個團隊沒有相同的成員，且兩個團隊共有全部的 $m$ 個卡通人物，
那這兩個團隊稱為互補團隊。

給 $n$ 個團隊，求有幾隊互補團隊。

輸入第一行有兩個整數 $m$、$n$，
接下來有 $n$ 行，每行有一個字串表示一個團隊。

輸出互補團隊的對數。

$2 \leq m \leq 26$
$1 \leq n \leq 50000$

## 說明
因為英文字母只有 26 個，
所以可以用一個數字來表示每個團隊有哪些成員：
當第一個位元（由右開始數）為 1 時，表示這個隊伍有 A 這個人，
當第二個位元為 1，表示有 B 這個人，依此類推，
舉例來說：10111₍₂₎ 的第一、二、三、五個位元是 1，
表示這個團隊有 ABCE 這四個人。

兩個互補團隊的數字互相 bitwise xor 後，應該要等於 $2^m-1$，
因為 $2^m-1_{(10)}$ 寫成二進位是 $m$ 個 1，
如果兩個數字中有同一個位元是 1（表示這兩隊有相同的人），
那麼 xor 後這個位元就會變成 0，
必須要其中一個數字的這個位元是 1，另一個是 0，xor 後才會是 1。

用這個方式，可以快速地找到可以配對的團隊，
接下來我們一邊讀一邊處理，
先用一個 map 來存出現過的每種團隊有幾個，
（包含的人都一樣就當作是一樣的團隊）
輸入一個團隊後，先把表示這個團隊的數字 $t$ 算出來，
接下來他可以跟所有為 $t$ xor $2^m-1$ 的團隊配，
這樣一來就可以算出能配出幾隊互補團隊。
> 若 a xor b = c
> 則 a xor c = b

時間複雜度 $O(n \log n)$。
（map 搜尋需要 $O(\log n)$ 的時間）

## Code

#include <bits/stdc++.h>
using namespace std;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m, n;
    cin >> m >> n;

    map<int, int> c;
    int all = (1 << m) - 1;
    int ans = 0;
    for(int i = 0; i < n; i++){
        string str;
        cin >> str;

        int t = 0;
        for(int j = 0; j < str.size(); j++){
            t |= (1 << (str[j] - 'A'));
        }
        
        ans += c[t ^ all];
        c[t]++;
    }
    cout << ans << "\n";

    return 0;
}