cf1097F(bitset+莫比乌斯反演)

2019-04-14 21:10发布

站内文章 / 模拟电子
10302 0 1729
题意：给定n个集合，要求支持4个操作： 1.将集合初始化成{v} 2.令集合Z=集合X∪集合Y 3.令集合Z={k|k=gcd(a,b),ain X,bin Y} 4.查询集合里面v出现的次数并模上2   终于放假了。。好久以前的题。。 答案只需要模2就很容易想到用二进制来表示，那么可以直接上bitset，那么合并相当于做一次模2加，直接异或就行了。。 然后对于操作3，可以直接维护因子出现的个数，维护因子出现次数为g(n)，若n在集合中出现f(n)次，那么 g(n)=sum_{n|d}f(d) 然后用 f(n)=sum_{n|d}g(d)mu(frac{d}{n}) 还原     /** *　　　　　　 　　┏┓　　 　┏┓ * 　　　　　 　　┏┛┗━━━━━━━┛┗━━━┓ * 　　　　　 　　┃　　　　　　　┃ 　 * 　　　　　 　　┃　　　━　　 　┃ * 　　　　　 　　┃　＞　　　＜　┃ * 　　　　　 　　┃　　　　　　　┃ * 　　　　　 　　┃...　⌒　... 　┃ * 　　　　　　 　┃ ┃ * 　　　　　　 　┗━┓ ┏━┛ * 　　　　　　　　　┃ ┃　Code is far away from bug with the animal protecting　　　　　　　　　　 * 　　　　　　　　　┃ ┃ 神兽保佑,代码无bug * 　　　　　　　　　┃ ┃　　　　　　　　　　　 * 　　　　　　　　　┃ ┃ 　　　　　　 * 　　　　　　　　　┃ ┃ * 　　　　　　　　　┃ ┃　　　　　　　　　　　 * 　　　　　　　　　┃ ┗━━━┓ * 　　　　　　　　　┃ ┣┓ * 　　　　　　　　　┃ ┏┛ * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛ * 　　　　　　　　　　┃┫┫ ┃┫┫ * 　　　　　　　　　　┗┻┛ ┗┻┛ */ #include #include #include #include #include #include #include #include #include #include #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,l,r) for(int i=l;i>=r;i--) #define link(x) for(edge *j=h[x];j;j=j->next) #define mem(a) memset(a,0,sizeof(a)) #define ll long long #define eps 1e-8 #define succ(x) (1<>1) #define NM 100005 #define nm 7005 #define pi 3.1415926535897931 const ll inf=1e9+7; using namespace std; ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return f*x; } int n,m,prime[nm],tot,mu[nm],_x,_y,_t; bool v[nm]; bitset<7005>a[NM],b[NM],c[nm],tmp; int main(){ //freopen("data.in","r",stdin); n=7000; inc(i,1,n){ for(int j=1;j*j<=n;j++)if(i%j==0)b[i].set(j),b[i].set(i/j); } mu[1]=1; inc(i,2,n){ if(!v[i])prime[++tot]=i,mu[i]=-1; inc(j,1,tot){ if(i*prime[j]>n)break; v[i*prime[j]]++; if(i%prime[j]==0){mu[i*prime[j]]=0;break;} mu[i*prime[j]]=-mu[i]; } } inc(i,1,n){ for(int j=i,k=1;j<=n;j+=i,k++)if(mu[k])c[i].set(j); } n=read();m=read(); while(m--){ _t=read();_x=read();_y=read(); if(_t==1){ a[_x]=b[_y]; }else if(_t==2){ _t=read(); a[_x]=a[_y]^a[_t]; }else if(_t==3){ _t=read(); a[_x]=a[_y]&a[_t]; }else{ tmp=a[_x]&c[_y]; printf("%d",(int)tmp.count()%2); } } putchar(' '); return 0; }       F. Alex and a TV Show time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output Alex decided to try his luck in TV shows. He once went to the quiz named "What's That Word?!". After perfectly answering the questions "How is a pseudonym commonly referred to in the Internet?" ("Um... a nick?"), "After which famous inventor we name the unit of the magnetic field strength?" ("Um... Nikola Tesla?") and "Which rock band performs "How You Remind Me"?" ("Um... Nickelback?"), he decided to apply to a little bit more difficult TV show: "What's in This Multiset?!". The rules of this TV show are as follows: there are

热门文章