[CF1466F] Euclid's nightmare - 并查集
Description
给定 n 个二进制 m 位串 ai,求他们的线性基的大小,保证每个元素只有不超过两个 1 其它都是 0(以及按照顺序将元素选入线性基得到的序列)
Solution
如果所有串都恰好有 2 个 1,那么我们可以对每个位建立一个结点,任何一个串就转化成了一条边,环意味着线性相关,因此求这个图的生成树即可
考虑那些有一个 1 的串怎么办,我们添加一个虚点,所有只有一个 1 的串向虚点连边即可,这样如果出现了 01,11,10 的情况,就会成环
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int N = 5e5 + 5;
int fa[N], n, t1, t2, t3, m;
int qpow(int p, int q)
{
return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
}
int find(int p)
{
return p == fa[p] ? p : fa[p] = find(fa[p]);
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i <= m; i++)
fa[i] = i;
vector<int> answer;
for (int i = 1; i <= n; i++)
{
cin >> t1 >> t2;
if (t1 == 1)
{
int p = find(t2);
int q = find(0);
if (p != q)
fa[p] = q, answer.push_back(i);
}
else
{
cin >> t3;
int p = find(t2);
int q = find(t3);
if (p != q)
fa[p] = q, answer.push_back(i);
}
}
int x = answer.size();
cout << qpow(2, x) << " " << x << endl;
for (auto x : answer)
cout << x << " ";
}