M_sea

CF1097F Alex and a TV Show
CodeForcesLuogu分析upd:根据 $\mathrm{\color{black}{x}\color{r...
扫描右侧二维码阅读全文
08
2019/04

CF1097F Alex and a TV Show

CodeForces

Luogu

分析

upd:根据 $\mathrm{\color{black}{x}\color{red}{gzc}}$ 的反馈,修改了一些内容。

很神仙的一道题,用到了 $\mathrm{bitset}$ + 莫比乌斯反演。

因为只关心奇偶性,考虑用 $\mathrm{bitset}$ 来维护。

然后?不会了啊qwq

还是对每个集合维护一个 $\mathrm{bitset}$ ,只是第 $i$ 位表示 $i$ 作为因数的出现次数的奇偶性。

于是 $1$ 操作的话,预处理后直接赋值即可; $2$ 操作直接异或即可; $3$ 操作直接与即可。

重点考虑 $4$ 操作怎么做。

设 $f(i)$ 表示 $i$ 作为因子的出现次数, $g(i)$ 表示 $i$ 的出现次数,那么有 $g(x)=\sum\limits_{x|d}f(d)$ 。

显然可以莫比乌斯反演一波,得到 $f(x)=\sum\limits_{x|d}\mu(\frac{d}{x})g(d)$ 。

维护一些 $\mathrm{bitset}$ ,假设叫 $\mathrm{Mu}$ 。设 $\mathrm{Mu}[i][j]\ (i|j)$ 表示 $\mu(\frac{j}{i})$ ,于是只要与一下,然后 $1$ 的个数就是答案了。

至于 $-1$ 怎么直接存,因为只关心奇偶性,所以 $\mu$ 值为 $-1$ 的可以视作 $1$ 。

具体实现和细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int L=7000+10;

int v[L],p[L],cnt=0;
int mu[L];
bitset<L> bit[N],Mu[L],S[L];

inline void sieve(int n) {
    v[1]=mu[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mu[i]=-1;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else break;
        }
    }
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;j+=i)
            S[j][i]=1,Mu[i][j]=(mu[j/i]!=0);
}

int main() {
    sieve(7000);
    int n=read(),Q=read();
    while (Q--) {
        int op=read();
        if (op==1) {
            int x=read(),y=read();
            bit[x]=S[y];
        }
        else if (op==2) {
            int x=read(),y=read(),z=read();
            bit[x]=bit[y]^bit[z];
        }
        else if (op==3) {
            int x=read(),y=read(),z=read();
            bit[x]=bit[y]&bit[z];
        }
        else {
            int x=read(),y=read();
            printf("%d",(bit[x]&Mu[y]).count()&1);
        }
    }
    return 0;
}
最后修改:2019 年 04 月 23 日 08 : 13 PM

发表评论