Cowpatibility (USACO Gold 2018 December)

朴素办法是1对1比较，复杂度 $\mathcal{O}(N^2)$ ，因为 $N=5 \cdot 10^4$ ，这个会TLE，需要考虑怎么优化。

关键条件当然是每个牛只喜欢5个flavor。怎么用这个条件？这里的技巧，就是可以用每头牛的5个flavor的集合来生成所有子集，如果另外一头牛和她兼容，那么至少会和她共享一个子集（这个办法是一个哈希的思路，类似Rolling hash或者Shingling），每头牛一共 $31N$ 个flavor的子集（ $2^5-1$ ）。

然后没有交集的pairs的数量可以用容斥原理计算：所有pairs - 同时喜欢1个flavor的所有pairs + 同时喜欢2个flavor的pairs - 3个的pairs + 4个的pairs - 5个的pairs。

所以用所有的子集（最多5头牛）作为索引，只要统计同时喜欢这个子集的牛的数量，就可以算出这个子集对应的正或负的贡献，全部加起来就行了。

解法比较巧妙，这个哈希求交集的计数方法需要掌握，将来类似方法可能会再次出现。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct S {
    int cnt;
    int f[5];       // zero-padded
};
bool operator<(const S a, const S b) {
    for (int i = 0; i < 5; i++) {
        if (a.f[i] < b.f[i])
            return true;
        if (a.f[i] > b.f[i])
            return false;
    }
    return false;
}
int n;
int a[50005][5];
map<S, int> ssets;
ll ans;
 
void subsets(int fl[]) {    // generate all subsets of 5 flavors
    for (int i = 1; i <= 31; i++) {
        S ss;
        memset(&ss, 0, sizeof(ss));
        int j = 0;
        for (int k = 0; k < 5; k++)
            if (i & (1 << k)) {
                ss.f[j++] = fl[k];
            }
        ss.cnt = j;
        ssets[ss]++;
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++) {
            scanf("%d", &a[i][j]);
        }
        sort(a[i], a[i]+5);
        subsets(a[i]);
    }
    ans = (ll) n * (n-1) / 2;
    for (auto e: ssets) {
        S s = e.first;
        int cows = e.second;
        if (cows <= 1) continue;
        int sign = s.cnt == 1 || s.cnt == 3 || s.cnt == 5 ? -1 : 1;
        ans += sign * (ll)cows * (cows-1) / 2;
    }
    printf("%lld", ans);
    return 0;
}