CF1735D Meta-set题解

· · 题解

读一读题目

给出 n 个 k 长的三进制串，求出合法五元集的个数。

五元集合法的条件是，能从中提取出合法三元集，数量超过 1。

而三元集合法的条件是：对于三个串的第 i 位，其数字要么都相等，要么分别为 0,1,2 不重复的数。

举一点点例子

0 0 1 1
0 2 0 1
0 1 2 1

比如，对于这组由长度为 4 的三进制串组成的三元集，从最左边那位看起，其数字为 0,0,0，皆相等，满足第一个条件，合法；对于从左数起的第二位，其数字为 0,2,1，三个数字不相等，不符合第一个条件，但是它们不重复，满足第二个条件，合法。后两位同理，亦满足条件。故该三元集合法。

而对于以下的五元集：

0 0 0 0 // a串
0 0 0 1 // b串
0 0 0 2 // c串
0 0 1 0 // d串
0 0 2 0 // e串

由上面的规则可知，a,b,c 串组成的三元集合法，a,d,e 串组成的三元集也合法。故该五元集能提取出两个合法三元集，所以整个五元集合法。

想一想思路

要求出合法五元集的个数，我们首先得求出合法三元集的个数。

求合法三元集

用一个两重循环进行遍历，循环变量 i,j 表示当前想要求出的三元集中包含了第 i 和第 j 个三进制串。

为了保证三元集满足条件，可以通过已知的 i,j 串得到第三个串，比如：

0 0 1 // 第i串
0 2 0 // 第j串

我们从左向右逐位求解，第一位为 0,0，则第三个串的第一位必须为 0；第二位为 0,2，则第三个串的第二位必须为 1；第三位为 1,0，则第三个串的第三位为 2。

故三元集里的第三个串为 0 1 2。

同时可以发现，已知两个串的前提下，三元集里的另一个串是唯一的。

于是，我们利用 map 数组判断推导出的第三个串是否存在，即可进行统计，用 sum 数组记录含有 i 串的合法三元集的个数。

求合法五元集

用一个循环遍历每一个三进制串。循环变量 i 表示当前所求的五元集中含有第 i 串。

为了使该五元集合法，五元集中必须能提取出至少两个的合法三元集。我们之前已经求出 sum 数组，记录含有 i 串的合法三元集的个数。于是当前第 i 串对结果的贡献就是 C_{sum_i}^{2}。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e3+4;
LL n,k,a[N][25],w[N],res,sum[N];
map <LL,int> mp;

LL make(LL p,LL q){
    LL r=0;
    for(LL j=1,t=1;j<=k;j++,t*=3){
        if(a[p][j]==a[q][j]){
            r+=a[p][j]*t;
        }
        else{
            r+=(3-a[p][j]-a[q][j])*t;
        }
    }
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(LL i=1;i<=n;i++){
        for(LL j=1,t=1;j<=k;j++,t*=3){
            cin>>a[i][j];
            w[i]+=a[i][j]*t; //记录每个三进制串对应的十进制数
        }
        mp[w[i]]=i; //记录该串对应的序号
    }

   //求合法三元集的个数
    for(LL i=1;i<=n-2;i++){
        for(LL j=i+1;j<n;j++){ //从i的下个串开始遍历，防止重复
            LL num=make(i,j); //求i串和j串对应的第三个串
            if(mp[num]>j){ 
            //该串的序号应该大于j，从而保证不重复判断
                sum[i]++;
                sum[j]++;
                sum[mp[num]]++;
            }
        }
    }
    //求合法五元集的个数，统计结果
    for(LL i=1;i<=n;i++){
        res+=sum[i]*(sum[i]-1)/2; 
    }
    cout<<res<<'\n';
}