AtCoder ARC #084 : F - XorShift

これは知識不足で解けない…。
https://beta.atcoder.jp/contests/arc084/tasks/arc084_d

問題

N個の非負整数が与えられる。
この集合に対し、以下の手順で要素を増やすことができる。

• 既存の要素を2倍したもの。
• 既存の２要素のxorを取ったもの。

こうして作成できる要素のうちX以下の物はいくつあるか。

解法

２要素のxorを取るということは、繰り上げ繰り下げを無視すれば加算減算ができるということになる。
また、既存要素の２倍というのは2進数でいえば桁を1つあげることに相当する。

よって、ある要素から別の要素の数倍を引く、すなわち剰余を取ることができ、剰余が取れるならユークリッドの互除法の要領でGCDが取れる。
そこでまず全要素のGCDを取ろう。

こうして得たGCDの２進数表記をPとする。
問題の手順を繰り返して生成できる集合は、Pの整数倍(ただし繰り上げは行わない)となる。
そのような整数のうちX以下の物を求めよう。

Pの２進数表記の桁数をdとする。
Pの倍数について、下からd桁目より上を定めれば、下(d-1)桁は一意に決まる。
よって、Xの下(d-1)桁を取り除いた２進数に関し、X未満となるPの倍数は1つずつ作れる。
そのためその分答えに勘案する。

Xの下(d-1)桁を取り除いた２進数がXと一致する場合に関しては、実際Pを整数倍してそのような整数を作ってみて、下(d-1)桁がXとPの倍数どちらが大きいか判定すればよい。

int N;
string S;
bitset<4000> X,P;
ll mo=998244353;
ll p2[202020];
int ng;

bitset<4000> gcd(bitset<4000> A,bitset<4000> B) {
	int i;
	for(i=3999;i>=0;i--) {
		if(A[i]==1 && B[i]==1) {
			B^=A;
			break;
		}
		if(A[i]==1) break;
		if(B[i]==1) {
			swap(A,B);
			break;
		}
	}
	
	// A>B
	while(1) {
		int x;
		for(x=i-1;x>=0;x--) if(B[x]) break;
		if(x<0) break;
		while(i>=x) {
			if(A[i]) A^=B<<(i-x);
			i--;
		}
		i=x;
		swap(A,B);
	}
	return A;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,101010) p2[i+1]=p2[i]*2%mo;
	
	cin>>N>>S;
	FOR(i,S.size()) if(S[i]=='1') X[S.size()-1-i]=1;
	FOR(j,N) {
		cin>>S;
		bitset<4000> B;
		FOR(i,S.size()) if(S[i]=='1') B[S.size()-1-i]=1;
		if(j==0) P=B;
		else P=gcd(P,B);
	}
	
	ll ret=0;
	FOR(i,4000) if(P[i]) x=i;
	bitset<4000> Y;
	for(i=3999;i>=x;i--) {
		if(X[i]) ret+=p2[i-x];
		if(X[i]^Y[i]) Y^=P<<(i-x);
	}
	
	ret++;
	for(i=x-1;i>=0;i--) {
		if(Y[i]<X[i]) {
			break;
		}
		if(Y[i]>X[i]) {
			ret--;
			break;
		}
	}
	
	cout<<ret%mo<<endl;
	
	
	
	
}

まとめ

GCDを取るという発想がなかったのでどうしようもない。
xorとshiftが出たら割り算とGCDを取るというアイデアは覚えておこう。