Codeforces 1097 F

有n(<=100000)个可重集合

有4种操作：

1.将x集合置为 ！只有 ！ v一个数

2.将x集合置为y+z

3.将x集合置为 y ∘ z y \circ z y∘z

其中 ( y ∘ z ) = gcd ⁡ ( a , b ) ∣ a ∈ y , b ∈ z (y \circ z) = {\gcd(a,b)|a \in y ,b \in z} (y∘z)=gcd(a,b)∣a∈y,b∈z

4.求x集合中值为v的元素的奇偶性。

题解：

因为是在mod 2意义下

发现可以用bitset优化2操作，即xor。

然后3操作是一个卷积，可以通过构造正变换和逆变换使得卷积变点乘，即and。

然后4操作可以发现只有7000种不同的操作，可以把操作表示为bitset，然后直接and取你要的位数，然后count就可以得出你要的答案。

至于这个变换。

设元素i有 f ( i ) f(i) f(i)个。

那么 F ( i ) = ∑ i ∣ p f ( p ) F(i)=\sum_{i|p}f(p) F(i)=i∣p∑​f(p)

可以发现这个 F F F是可以点乘的。

逆变换就是 f ( i ) = ∑ p ∣ i m u ( p i ) ∗ F ( p ) f(i) =\sum_{p|i} mu(\frac pi)*F(p) f(i)=p∣i∑​mu(ip​)∗F(p)

这个逆变换也可以也可以转化成bitset的and

真是涨了各种bitset的用法啊。

可是快速莫比乌斯变换已经是个专属名词了，那这个变换叫什么呢。

#include<bits/stdc++.h>
#define maxn 100005
#define SET bitset<7001>
using namespace std;

int n,q;
SET a[100005],mu,mup[7001],tmp;
int pr[7005],cnt_pr;
bool vis[7006];

int main()
{	
	scanf("%d%d",&n,&q);	
	mu[1]=1;
	for(int i=2;i<=7000;i++)
	{	if(!vis[i]) pr[cnt_pr++]=i,mu[i]=1;
		for(int j=0;pr[j]*i<=7000;j++)
		{
			vis[i*pr[j]]=1;
			if(i%pr[j]==0) break;
			mu[i*pr[j]]=mu[i];
		}
	}
	
	for(int i=1;i<=7000;i++)
		for(int j=i;j<=7000;j+=i)
			mup[i][j]=(1 & mu[j/i]);
	for(;q--;)
	{
		int x,y,z,op;
		scanf("%d",&op);
		scanf("%d%d",&x,&y);
		if(op==1)
		{
			a[x].reset();
			for(int i=1;i*i<=y;i++)
				if(y%i==0){
					a[x][i]=(a[x][i]^1);
					if(i*i!=y) a[x][y/i]=(a[x][y/i]^1);
				}
		}
		if(op==2)		
		{
			scanf("%d",&z);
			a[x] = a[y] ^ a[z];
		}
		if(op==3)
		{
			scanf("%d",&z);
			a[x] = a[y] & a[z];
		}
		if(op==4)
		{
			tmp = a[x] & mup[y];
			printf("%d",tmp.count()&1);
		}
	}
}