CF1735D Meta-set

· · 题解

赛时缺个脑子痛失 D 题，赛后看了一会儿莉可丽丝等 System Test 完了之后补了这道题。

 

下面称题中的 set 为「合法三元集」，meta-set 为「合法五元集」。

易见，一个合法三元集可以被其中任意两个元素唯一确定。由此我们可以得到以下三点：

  1. 枚举第一个和第二个元素，找第三个元素，就可以遍历所有的合法三元集，从而统计每一个元素在多少个合法三元集里；

  2. 对于一个元素所在的所有不同合法三元集，其两两交集均只含这一个元素；

  3. 一个合法五元集的任意两个不同合法三元子集，其交集大小必然不超过 1。

由上面第 3 条，又显然一个五元集的任意两个不同三元子集必然有交，我们可以知道每一个合法五元集里的任意两个不同合法三元子集交集大小为 1。

进一步地，在一个合法五元集里划出两个交集大小为 1 的合法三元子集，易见再在这个五元集里任意划出一个三元子集，其与现有这两个合法三元子集的交集大小不可能都为 1，从而可知一个合法五元集有且只有两个合法三元子集。

这样，我们枚举作为交集元素的那个元素，统计以其作为交集元素的所有合法五元集数量，即可得到答案。

时间复杂度 O(kn^2) 或 O(kn^2\log n)，取决于枚举前两个元素找第三个元素时使用的数据结构带不带 \log。

 

参考实现：

#include<bits/stdc++.h>

using namespace std;

int n, k, a[1007][22], cnt[1007];
long long s, ans;
map<long long, int> ap;

inline long long dmn(int x, int y)
{
    long long s = 0;
    for(int i = 1; i <= k; i++)
        s = s * 3 + ((a[x][i] == a[y][i]) ? a[x][i] : (3 - a[x][i] - a[y][i]));
    return s;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) cin >> a[i][j], s = s * 3 + a[i][j];
        ap[s] = i, s = 0;
    }

    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j)
        cnt[i] += (ap.find(s = dmn(i, j)) != ap.end() && ap[s] != i && ap[s] > j);
    for(int i = 1; i <= n; i++) if(cnt[i]) ans += 1ll * cnt[i] * (cnt[i] - 1) / 2;

    cout << ans;

    return 0;
}