Codeforces 1097F (Bitset+位运算技巧+莫比乌斯反演)

发表于 | 分类于 | | + s

Codeforces 1097F
题意：给$n(n\leq 10^5)$个multiset，然后进行如下操作：
1 x v：把第$x$个multiset变成${v}$
2 x y z：把第$x$个multiset变成$y∪z$
3 x y z：把第$x$个multiset变成如下内容：$gcd(a,b)|a∈y,b∈z$
4 x v：查询$v$在第$x$个multiset里出现的次数奇偶性

只关注奇偶性所以想到了bitset……
然后刚开始我发现$gcd$操作可以反演/容斥去做……然后跪了
看别人代码发现只需要对询问进行反演即可。。
维护$f_x(i)$为第$x$个multiset中$i$倍数的个数。
那么显然$y∪z$等价于$f_y(i)+f_z(i)$，$gcd(a,b)|a∈y,b∈z$等价于$f_y(i) \times f_z(i)$
然后根据位运算的技巧，$xor​$是不进位的加法，$and​$是不进位的乘法，所以上面操作
$f_y(i)+f_z(i) \Leftrightarrow f_y(i) xor f_z(i)$
$f_y(i) \times f_z(i) \Leftrightarrow f_y(i) and f_z(i)$

然后考虑怎么询问答案。设$g(i)$为$i$的个数。
我们已经维护了$f_x(i)$为第$x$个multiset中$i$倍数的个数，那么根据反演：
$$
g(i)=\sum_{d=1}^{\lfloor \frac ni \rfloor} \mu(d)g(di)
$$
即可求出。对于反演式子中的乘法，可以预处理$bitset$的$\mu$，然后做$and$运算，加法即为最后得到的$bitset$中的$1$的个数。

知识点：
1、bitset的空间计算方式为位数除以8
2、$xor$是不进位的加法，$and$是不进位的乘法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    bitset<7001 > bs[100000 + 5], gg[7005], hh[7005];
    // bs 即为上述 f, gg 为预处理的 mu, hh 为预处理的倍数

    int n, q, mu[7005], pri[7005], vis[7005], tot;

    void clean() {
        ms(vis, 0), tot = 0;
    }
    int solve() {

        clean();

        mu[1] = 1;
        for (int i = 2; i <= 7000; ++i) {
            if (!vis[i]) vis[i] = 1, pri[++tot] = i, mu[i] = -1;
            for (int j = 1; j <= tot && 1ll * pri[j] * i <= 7000ll; ++j) {
                vis[i * pri[j]] = 1;
                if (i % pri[j] == 0) {
                    mu[i * pri[j]] = 0;
                    break ;
                } else mu[i * pri[j]] = mu[i] * mu[pri[j]];
            }
        }
        for (int i = 1; i <= 7000; ++i) 
        for (int j = i; j <= 7000; j += i) hh[j][i] = 1, gg[i][j] = ((mu[j / i] == 0) ? 0 : 1); // 加减 1 等价

        scanf("%d%d", &n, &q);

        while (q--) {
            int ty, x, y, z, v; scanf("%d", &ty);
            if (ty == 1) 
                scanf("%d%d", &x, &v), bs[x] = hh[v];
            if (ty == 2)
                scanf("%d%d%d", &x, &y, &z), bs[x] = bs[y] ^ bs[z];
            if (ty == 3)
                scanf("%d%d%d", &x, &y, &z), bs[x] = bs[y] & bs[z];
            if (ty == 4)
                scanf("%d%d", &x, &v), printf("%d", (int)((bs[x] & gg[v]).count() & 1));
        }
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------