kmjp's blog

競技プログラミング参加記です

Hello 2019 : F. Alex and a TV Show

本番辛うじて解けた。
https://codeforces.com/contest/1097/problem/F

問題

N個のmultiset S[i]がある。初期状態はいずれも空である。
以下のクエリに順次答えよ。

  • あるS[i]を指定された1要素{x}だけのmultisetにする。
  • S[x]をS[y] ∪ S[z]で置き換える。
  • S[x]をS[y]とS[z]の積集合で置き換える。これはa∈S[y],b∈S[z]であるa,bに対し、GCD(a,b)からなる|S[y]|*|S[z]|要素からなる集合とする。
  • S[x]内にvが奇数個あるか答える。

解法

集合内における数値の数は偶奇だけ把握できればいいので、multisetをbitsetで持つことにする。
その際、例えば1番目のクエリではS[i][x]だけ1にするのではなく、xの約数dについてS[i][d]=1とするようにする。
これはGCDの操作によりxの約数が必要となるケースに備えた処理である。

そうすると以下のように表現できる。

  • 和集合は、bitsetのxorで表現できる。
  • 積集合は、bitsetのandで表現できる。
  • vが奇数である条件は、bitsetのうち、vの倍数mに関しメビウス関数μ(m/v)!=0となるmにおけるbitの個数が奇数個

事前に約数の列挙やメビウス関数の計算を済ませておけば、全体でO(Q*max(x)/w)で済む。

int N,Q;
bitset<8192> T[7070],U[7070];
bitset<8192> S[101010];

int ok[7070];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	
	
	for(i=1;i<=7000;i++) {
		for(x=1;x<=i;x++) if(i%x==0) T[i][x]=1;
		
		ok[i]=1;
		for(x=2;x*x<=i;x++) if(i%(x*x)==0) ok[i]=0;
	}
	for(i=1;i<=7000;i++) {
		for(x=i;x<=7000;x+=i) if(ok[x/i]) U[i][x]=1;
	}
	
	scanf("%d%d",&N,&Q);
	
	string R;
	while(Q--) {
		int v,z;
		scanf("%d%d",&i,&x);
		x--;
		if(i==1) {
			scanf("%d",&v);
			S[x]=T[v];
		}
		else if(i==2 || i==3) {
			scanf("%d%d",&y,&z);
			y--,z--;
			if(i==2) S[x]=S[y]^S[z];
			if(i==3) S[x]=S[y]&S[z];
		}
		else {
			scanf("%d",&v);
			auto a=S[x]&U[v];
			R+=(char)('0'+(a.count()%2));
		}
	}
	cout<<R<<endl;
	
	
}

まとめ

本番メビウス関数が出てこず、実験して各ビットがvの判定にどうかかわるか求めた。