Codeforces Round #824 D. Meta-set(组合数学)

Codeforces Round #824 D. Meta-set(组合数学)

性质

• 两个card唯一确定另一个card
• 两组set至多重合一个card，根据性质1反证，若重两个card，显然两个set重合。
• 对于meta-set，若(c1,c2,c3)为一个set，那么根据性质2，(cx,c4,c5)为另一个set($x\in [1,2,3]$) 即只能重合一个card。
• 那么我们可以枚举重合的card，那么计算两两包含它的set，假设包含它的set个数为$x$，那么它的贡献是：$\frac{x(x-1)}{2}$
• 这样算是不会重复的，假设(c1,c2,c3)为一个set，s3为我们枚举的，那么(c4,c5) 只能与c1,c2,c3中的一个组合。因此(c1,c3, c2)和(c1,c3,c2) 不可能同时对应(c4,c5)。

时间复杂度：$O(k{n}^2)$

#include <bits/stdc++.h>
 
using namespace std;
 
#define F first
#define S second
typedef long long       ll;
typedef long double     ld;
typedef pair<ll, ll>   pll; 
typedef pair<int, int> pii; 
 
const long long kk = 1000;
const long long ml = kk * kk;
const long long mod = ml * kk + 7;
const long long inf = ml * ml * ml + 7; 
#ifdef DEBUG
	mt19937 rng(1033);
#else
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());	
#endif
int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }
 
 
bool viv = false;
int n, k;
vector<vector<int>> v;
 
vector<int> get_comp(vector<int> a, vector<int> b) {
	vector<int> res(k);
	for (int i = 0; i < k; i++)
		res[i] = (6 - (a[i] + b[i])) % 3;
	return res;
}
 
void solve() {
	cin >> n >> k;
	v.resize(n);
	for (auto &vec : v) {
		vec.resize(k);
		for (auto &i : vec)
			cin >> i;
	}
	map<vector<int>, int> cnt;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			auto comp = get_comp(v[i], v[j]);
			cnt[comp]++;
		}
	}
	ll ans = 0;
	for (auto vec : v) {
		ans += (ll)cnt[vec] * (cnt[vec] - 1) / 2;
	}
	cout << ans << 'n';
}
 
int main() {
	// viv = true;
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(20);
	int t = 1; 
	// cin >> t;
	while (t--)
		solve();
 
	#ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	#endif
}

最后

以上就是发嗲柚子为你收集整理的Codeforces Round #824 D. Meta-set(组合数学)的全部内容，希望文章能够帮你解决Codeforces Round #824 D. Meta-set(组合数学)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。