「CF1287B」Hyperset

传送门

不难发现如果我们确定了三个串中的其中两个，那么合法的第三个串就是唯一的。

那么我们考虑枚举两个串 (i, j)，设对应的唯一合法第三串为 (k)，那么我们就只要算 (i) 前面有几个 (k) 就好了。

这个东西开个 map 就好了。

参考代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;

const int _ = 1505;

int n, k; string s[_]; map < string, int > t;

int main() {
#ifndef ONLINE_JUDGE
    freopen("cpp.in", "r", stdin), freopen("cpp.out", "w", stdout);
#endif
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) cin >> s[i];
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            string str = "";
            for (int o = 0; o < k; ++o) {
                if (s[i][o] == s[j][o]) str += s[i][o];
                else {
                    if (s[i][o] != 'S' && s[j][o] != 'S') str += 'S';
                    if (s[i][o] != 'E' && s[j][o] != 'E') str += 'E';
                    if (s[i][o] != 'T' && s[j][o] != 'T') str += 'T';
                }
            }
            ans += t[str];
        }
        ++t[s[i]];
    }
    printf("%lld
", ans);
    return 0;
}