読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.183 たのしい排他的論理和(EASY)

問題はこちら
No.183 たのしい排他的論理和(EASY) - yukicoder

・ちょっと難しい話
a[i]たちを(Z/2Z)^15のベクトルと見れば、bitxorがZ/2Z上の(従って(Z/2Z)^15上の)加法になっていることから問題は
「Z/2Z上のベクトル空間(Z/2Z)^15の部分集合{a[i]}が与えられた時、それが生成する部分空間には何個の元が属するか」と同値
(Z/2Z)^15のn次元部分空間の元の個数は(#(Z/2Z))^nなので、{a[i]}が生成する部分空間の次元を求めれば良い。
即ち{a[i]}の一次独立な元の最大個数を求めればよく、掃き出し法による上三角化で求めることができる

以下、本質的には同じだけど、この問題を解くときに実際に考えていたこと

・考察
x[i](0≦i≦14)が任意のiについて「x[i]は0または、最上位bitがibit目であるような値」を満たすとする
(つまりx[i]=0または2^i≦x[i]<2^(i+1))
S={i|x[i]≠0}とおくと、x[i]たちにbitxorを用いて作ることができる数の種類は2^#Sとなる
なぜなら∀i∈Sに対してibit目を決めたとき、上位bitから順に決めることを考えるとそれを実現するようなx[i]たちの使い方はちょうど1通りであり、このときSに属さないiに対してibit目はx[i]たちから1通りに決まるからである。
ということでSを、即ちx[i]たちをa[i]たちから作り上げればよいことが分かる。(Sがx[i]の作り方によらないことの証明は略す)
i≠jに対しa[i]をa[i] bitxor a[j]で置き換えても問題ないことから、数の集合Aが与えられた時x[i]は次のような手順で求めることができる
1:Aの全ての元が0なら終わり。さもなくば最大元aをとり最上位bitがibit目であるとする
2:x[i]をaとし、Aの元xであって、ibit目が1であるようなものを x bitxor a と置き換え、手順1にもどる
(手順2によりAの全ての元は2^i未満となったので、この再帰はいずれとまる)

よく考えればこれは別に最大元を取ってくる必要はなく、最大元と最上位bitが等しいものなら良いことが分かる。
さらに考えれば、任意にa∈Aをとりその0でないbitの1つをibit目としたとき、Aの数全体のibit目と上位bitを入れ替えたと考えれば、最初に取るものは何でも良いことがわかるので、手順は次のように書き換えられる
1:Aの全ての元が0なら終わり。さもなくば0でないAの元aを任意にとり、その0でないbitの1つをibit目とする
2:x[i]をaとし、Aの元xであって、ibit目が1であるようなものを x bitxor a と置き換え、手順1にもどる

ということでこれを実装

int main(){
	int n,i,j,k,s=0,a[5010],x[15]={};
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	for(j=0;j<n;j++){
		if(a[j]==0)continue;
		for(i=0;!(a[j]>>i&1);i++);
		x[i]=a[j];
		s++;
		for(k=j+1;k<n;k++)if(a[k]>>i&1)a[k]^=a[j];
	}
	printf("%d",1<<s);
	return 0;
}

もっと考えれば、この操作は全てのa[i]たちに対して同時に行う必要はなく、Aから取ってきた値に対して逐次行ってもよいことが分かる。即ち
1:全ての値を読み込んだなら終わり。さもなくば新しく読み込んだ値をaとする
2:aが0なら手順1に戻る。さもなくばaの0でないbitの1つをibit目とする
3:x[i]が0ならx[i]をaとし手順1に戻る。さもなくばaをa bitxor x[i]ととりかえて手順2に戻る

p,i,x[15];
main(s){
	for(gets(&p);~scanf("%d",&p);){
		while(p){
			for(i=0;~p>>i&1;i++);
			x[i]?p^=x[i]:(x[i]=p,s*=2,p=0);
		}
	}
	i=!printf("%d",s);
}

これを縮める

p,i,x[15];
main(s){
	for(gets(x);~scanf("%d",&p);)for(i=0;p^=p>>i++&1?!x[i]?s*=2,x[i]=p:x[i]:0;);
	i=!printf("%d",s);
}

113B