Good Bye 2020 : F. Euclid's nightmare

ようやく2020年の最後。
https://codeforces.com/contest/1466/problem/F

問題

N個の、m bit vectorが与えられる。
ただし、各vectorは1が立っている箇所が1個か2個である。

これらのxorで作れるvectorの数と、それらを構成する最小のvectorの集合を求めよ。

解法

結局基底ベクトルを求める問題である。
M要素のunion-findを用いる。
2bit立っているvectorがあるとき、対応する2つの位置をuniteしよう。
もし連結成分内に、s要素あり、その中に1個でも1bitだけ立っている要素があれば、2^s通りのベクトルを生成可能である。そうでない場合、2^(s-1)通りのベクトルを生成可能である。

int N,M;
vector<int> S[505050];
const ll mo=1000000007;
template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1010101> uf,uf2;
int SG[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&M);
	
	vector<int> V;
	FOR(i,N) {
		scanf("%d",&j);
		scanf("%d",&x);
		x=uf[x-1];
		if(j==2) {
			scanf("%d",&y);
			y=uf[y-1];
		}
		if(j==1) {
			if(SG[x]==0) {
				SG[x]=1;
				V.push_back(i+1);
			}
		}
		else {
			if(x!=y) {
				if(SG[x]==0||SG[y]==0) {
					SG[x]=SG[y]=SG[x]|SG[y];
					V.push_back(i+1);
				}
				uf(x,y);
			}
		}
		
	}
	
	
	
	ll ret=1;
	FORR(v,V) ret=ret*2%mo;
	cout<<ret<<" "<<V.size()<<endl;
	FORR(v,V) cout<<v<<" ";
	cout<<endl;
}

まとめ

問題文が無駄にややこしい。