CF 1735 D. Meta-set

JustACommonMan / 2023-06-17 / 原文

题目链接：https://codeforces.com/contest/1735/problem/D
代码链接：https://codeforces.com/contest/1735/submission/209958432

给定n个长度为k的串（互不相同），求合法五元集的数量
合法五元集定义为至少包含超过1个合法三元集
合法三元集定义为三个串，三个串的属性要么全部相同，要么互不相同，每个属性互相独立
显然，一个合法五元集只包含两个合法三元集：
$\quad$ 一个合法三元集中的两个串可以唯一确定另一个串
$\quad$ 所以一个合法五元集只能是由两个包含着同一个串的合法三元集组成
解法：
$\quad$ 二重循环枚举两个串，O(k)计算出另一个串，sum[i]记录包含第i个串的合法三元集的数量
$\quad$ 最后答案就是枚举每一个串，对于第i个串，从包含第i个串的合法三元集中选出两个构成合法五元集，求和即可
$$ans = \sum_{0}^{n-1} sum[i] \times (sum[i] - 1) / 2$$

点击查看代码

/*
    给定n个长度为k的串（互不相同），求合法五元集的数量
    合法五元集定义为至少包含超过1个合法三元集
    合法三元集定义为三个串，三个串的属性要么全部相同，要么互不相同，每个属性互相独立
    显然，一个合法五元集只包含两个合法三元集：
        一个合法三元集中的两个串可以唯一确定另一个串
        所以一个合法五元集只能是由两个包含着同一个串的合法三元集组成
    解法：
        二重循环枚举两个串，O(k)计算出另一个串，sum[i]记录包含第i个串的合法三元集的数量
        最后答案就是 枚举每一个串，对于第i个串，从包含第i个串的合法三元集中选出两个构成合法五元集，求和即可
        ans = \sum_{0}^{n-1} sum[i] \times (sum[i] - 1) / 2
*/
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(void)
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector< vector<int> > a(n, vector<int>(k));
    vector<i64> val(n, 0);
    map<i64, int> id;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++){
            cin >> a[i][j];
            val[i] = val[i] * 3 + a[i][j];
        }
        id[val[i]] = i;
    }
    vector<int> sum(n, 0); //包含第i个串的合法三元集的个数
    function<i64(int, int)> getval = [&] (int x, int y){
        i64 ret = 0;
        for(int i = 0; i < k; i++){
            if(a[x][i] == a[y][i]){
                ret = ret * 3 + a[x][i];
            }else{
                ret = ret * 3 + 3 - (a[x][i] + a[y][i]);
            }
        }
        return ret;
    };
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            i64 tem = getval(i, j);
            if(id[tem] > j){
                sum[i]++;
                sum[j]++;
                sum[id[tem]]++;
            }
        }
    }
    i64 ans = 0;
    for(int i = 0; i < n; i++){
        ans += sum[i] * (sum[i] - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}