本番辛うじて解けた。
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の判定にどうかかわるか求めた。