CF1735D Meta-set 题解

题目大意

给定 \(n\) 张卡牌，每张卡牌有 \(k\) 个属性，第 \(i\) 张卡牌的第 \(j\) 个属性为 \(c_{i,j}\)。

一个由 \(3\) 张卡牌 \(x,y,z\) 组成的集合被称作好的，当且仅当对于 \(1 \leq i \leq k\) 均有 \(c_{x,i}=c_{y,i}=c_{z,i}\) 或者 \(c_{x,i},c_{y,i},c_{z,i}\) 两两不相等。

一个 meta-set 由五张卡牌组成，且其中至少存在两个大小为 \(3\) 的子集是好的。求 meta-set 数量。

给出的卡牌两两不同。

数据范围为 \(n \leq 1000\)，\(k \leq 20\)，\(0 \leq c_{i,j} \leq 2\)。

观察

1. 注意到 \(c\) 只有 \(0,1,2\) 两个取值，所以一个好的集合要么对应位相等，要么分别为 \(0,1,2\)。
2. 一个 meta-set 应当恰好有 \(2\) 个大小为 \(3\) 的子集是好的，证明比较简单。
3. 必然有一张卡牌存在于两个好的集合当中。
4. 一个 meta-set 如果由 \((q,w,e,r,t)\) 组成，且 \(q\) 包含于两个 meta-set，那么比如满足 \((q,w,e)\) 和 \((q,r,t)\) 是好的集合。
5. 一张卡牌可以用 \(\sum _{i=1}^k c_{x,i} \times 3^{i-1}\) 表示。

求解

通过观察得到的 \(3\) 性质，我们枚举这一张卡牌是 \(x\)，根据 \(4\) 现在问题就变为统计有多少个好的集合包含了 \(x\)，记为 \(f_x\)。

因为 \(n\) 很小，我们直接枚举一个好的集合当中的另一张卡牌，我们可以直接推出另一张卡牌是什么，对于每一张卡牌我们用一个数来表示丢进 map 中计数就行了，时间复杂度 \(O(n^2 \log n)\)。

#include<bits/stdc++.h>

#define int long long

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define NO puts("No")
#define YES puts("Yes")

using namespace std;

namespace IO{
	inline int read(){
		RI X=0, W=0;register char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 1e3+5;
const int mod1 = 998244353;
const int mod2 = 1e9+7;
const int inf = 1e12;

int n, k, m[MAXN][25], v[25];

map<int,int> T;

inline void solve(){
	cin >> n >> k;
	int c=0, powc;
	for(int i=1;i<=n;++i){
		powc=1;c=0;
		for(int j=1;j<=k;++j){
			m[i][j]=read();
			c=c+powc*m[i][j];
			powc=powc*3;
		}
		T[c]++;
	}
	ll ans=0;
	int tot=0;
	for(int i=1;i<=n;++i){
		tot=0;
		for(int j=1;j<=n;++j){
			if(i==j) continue;
			c=0, powc=1;
			for(int p=1;p<=k;++p){
				if(m[i][p]==m[j][p]) v[p]=m[i][p];
				else v[p]=3-m[i][p]-m[j][p];
				c+=powc*v[p], powc*=3;
			}
			tot+=T[c];
		}
		tot/=2;
		if(tot==1) continue;
		ans=ans+tot*(tot-1)/2;
	}
	cout << ans;
	return ;
}

signed main(){
	solve();
	return 0;
}