0. 前言

//整数，string和char数组可以强制类型转换成bitset
//不支持迭代器
//类似string，可以存入unordered_set/map，可以用cin/cout输入输出
//转化为整数时0为最低位，转化为字符串时顺序与原先顺序相同，输出时从高位到低位输出

bitset<N>b;//定义初始值全为0的bitset，N为整型常量
bitset<N>b(x);//用无符号整型x初始化bitset，不超过unsigned long long范围
bitset<N>b(s);//用s初始化b，s可以是basic_string类型或bitset类型，若为basic_string类型则s中只能包含'0'或'1'
bitset<N>b(s,p);//用s从p位置开始到末尾初始化b，此处s只能为basic_string类型，下同
bitset<N>b(s,p,n);//用s从p开始的n个数初始化b，p和n都是整数

b=b2,b==b2,b!=b2;//b赋值为b2，b与b2是否相等，是否不等
b&b2,b|b2,b^b2,b<<n,b>>n,~b;//位运算，返回bitset类型
b&=b2,b|=b2,b^=b2,b<<=n,b>>=n;//位运算赋值

b[p],b.test(p);//下标访问。test会检查越界抛出异常，但返回为右值不能修改
b.flip(p),b.set(p),b.set(p,x),b.reset(p);//取反第p位，第p位设为1，第p位设为x，第p位设为0，O(1)
b.flip(),b.set(),b.reset();//所有位取反，所有位设为1，所有位设为0，O(n/w)
b.to_ulong(),b.to_ullong();//分别返回unsigned long和unsigned long long类型，表示将bitset转为整数，to_ullong需要C++11
b.to_string();//bitset转字符串
b.size(),b.any(),b.none(),b.all();//b的大小，是否存在1，是否全为0，是否全为1，all需要C++11，复杂度均为O(1)
b.count();//b中1的个数，O(n/w)
b._Find_first(),b._Find_next(p);//返回b中第一个1的位置，返回b中p以后不含p第一个1的位置，若不存在返回b的大小，O(n/w)

bitset 的原理实际上就是将 $w$ 个 bool 压到一个整形变量中，每次操作我们同时对 $w$ 个 bool 操作，使时间常数除以 $w$ ，通常 $w$ 等于 32 或 64，取决于你是 32 位还是 64 位。

同时显然可以优化空间。

1. DP

bitset 可以优化可行性 DP，也就是值为 $0/1$ 的 DP，这一类中最常见的就是背包问题。

CF1239E Turtle

首先考虑给定矩阵，如何刻画乌龟的路径，有性质：乌龟走的一定是第一行从开头的一段的连续路径，然后下去走到头。故设 $pre_{i}$ 表示第一行的前缀和， $suf_{i}$ 表示第二行的后缀和。那么答案就是 $\max_{i}\{pre_{i}+suf_{i+1}\}$ 。

考虑重排操作有没有什么性质，有一个贪心的想法，我们让第一行从小到大排序，第二行从大到小排序，这样列列操作一定是最优的，证明考虑从逆序对入手进行反证法即可。然后问题转化为行行之间刻画，可以考虑利用 DP 进行计算，但是代价计算是 $\max_{i}\{pre_{i}+suf_{i+1}\}$ 。我们没法进行转移啊！

考虑简化代价，我们考虑排序的会对乌龟的决策带来什么决策，关键性质：乌龟要么在开头就往下走然后走完第二行，要么走完第一行然后往下走走到终点。

那么代价可以简化成： $a(1,1)+a(2,n)+\max\{\sum\limits_{i=2}^{n}a(1,i),\sum\limits_{i=1}^{n-1} a(2,i)\}$ 。前面是固定的，后面是不固定的。直接飞上去 DP 进行决策：设 $f(i,j,k)$ 表示考虑到第 $i$ 个数，第一行一共选了 $j$ 个数，选出数的总和 $k$ 是否可能。最后让总和尽可能对半分即可。

注意到这个是可行化 DP，但是值域和 $n$ 极小，可以用 bitset 优化，时间复杂度 $O(\dfrac{1}{w}n^2 \sum\limits a)$ 。

CF1481F AB Tree

注意到答案很奇怪，写个暴力（自从那个构造之后就有写暴力发现性质）发现答案上界在最大深度和最大深度加 $1$ 之间徘徊。

考虑分析最优解构造，注意到答案和深度有关。考虑按层构造，每一层我们尽量填入相同的字符，设出现次数较大的字符为 $c$ ，因为要降低对儿子的影响，所以把非叶节点填入颜色 $c$ ，设 $m$ 为未填写的字符，因为非叶节点的出现次数 $\le \dfrac{m}{2}$ ，而 $c\ge \dfrac{m}{2}$ ，所以一定能填满，然后把 $c$ 填入这一层的叶节点，剩下的就只有另一种颜色的，填入到其它点中，不难发现只有当前层会多一种不同的字符。

那么现在问题转化为能不能每一层都能填写相同字符,若可行输出用 DP 求解答案并输出方案，否则贪心按照上述方法构造即可。

不难发现这个 DP 可以当作背包 DP，把每一层的节点数量当作物品，那么这就是一个多重背包可行性问题。直接做是 $O(n^2)$ 的，但是发现物品种类数最多 $O(\sqrt{n})$ 级别的（。可以通过 bitset 加二进制分组优化到 $O(\dfrac{n\sqrt{n}}{w})$ ，输出方案可以加个回溯也是 ok 的。

我写的是 $O(n\sqrt{n})$ 的神秘完全背包做法：题解：CF1481F AB Tree - 洛谷专栏

2. 矩阵乘法

当矩阵乘法取值只有 0 或 1 时，考虑 bitset 优化：

CF576D

又是特殊限制，我们还是设 DP。

设 $f(i,j)$ 表示在第 $i$ 个点，在走过的边数为 $j$ 的情况下是否能够到达（取值为 0 或 1），由 $j-1$ 可以转移过来，并且矩阵味很重，转移是或的关系，可以考虑矩阵优化。

考虑无解的情况怎么做，不妨假设 1 号节点边都可以走，如果都可以走的情况下还是到不了那就 GG。

我们根据操作手册，发现在第五步就炸了，因为每一次 $d_i$ 的更新都需要重新设置转移矩阵，考虑根据 $d_i$ 的变化量进行快速幂，每一次中断跑多源 BFS 更新答案，让后就做完了。

我们不难发现 $f$ 的取值只有 0 或 1，可以利用 bitset 优化，写的时候如下：

struct Matrix{
    bitset<MN> mat[MN];

    Matrix(int x=0){
        for(int i=0;i<MN;i++){
            for(int j=0;j<MN;j++){
                mat[i][j]=0;
            }
        }
        if(!x) return;
        for(int i=0;i<MN;i++) mat[i][i]=x;
    }

    Matrix operator*(const Matrix &x)const{
        Matrix ret;
        for(int i=0;i<MN;i++){
            for(int k=0;k<MN;k++){
                if(mat[i][k]){// 把j省去了
                    ret.mat[i]|=x.mat[k];
                }
            }
        }
        return ret;
    }

};

3. 异或方程组

异或方程组就是模 2 意义下的线性方程组，所有未知数取值为 0 或 1，已知条件形如若干个未知数异或值为 0 或 1。

bitset 可以优化高斯消元，时间复杂度 $O(\dfrac{n^3}{w})$ 。

和一般的高斯消元一样从前到后依次消每一列。

bitset<MN> bit[MN];

int gauss(int n,int m){
    int ans=-1;
    for(int i=1;i<=n;i++){
        int cur=i;
        while(cur<=m&&!bit[cur].test(i)){
            cur++;
        }
        if(cur>m) return 0;
        ans=max(ans,cur);
        if(cur!=i) swap(bit[cur],bit[i]);
        for(int j=1;j<=m;j++){
            if(i!=j&&bit[j].test(i)){
                bit[j]^=bit[i];
            }
        }
    }
    return ans;
}

P2447 [SDOI2010] 外星千足虫 - 洛谷

4. 字符串匹配

bitset 可以在 $O(\dfrac{nm}{w})$ 的时间复杂度内求解字符串匹配，在 m 较小时比 kmp 更优秀，而且支持带修，具体的我们维护每个字符在哪些位置上出现过，记 $i$ 字符出现在 $b_{i}$ 集合的位置，现有匹配串 $st$ ，维护当前仍然合法的起始点集合 $pos$ ，则有 $pos=pos \land (b_{st_i}>>i)$ 。

CF914F Substrings in a String

bitset 好神秘！

对 26 个字母各开一个 bitset，存这个字母出现的位置。

对于询问，新建一个 bitset。从前到后枚举询问串的每个位置 yi，和这个字母对应的 bitset 右移 i 位取 and。

最终得到的 bitset 中 1 的个数即为询问串在原串出现次数。

P4465 [国家集训队] JZPSTR

bitset，bitset，bitset！

虽然标程是分块加 SAM，但是显然大家都不喜欢这么毒瘤的。注意到插入删除询问次数独立的都很少，并且字符集很少，考虑 bitset。我们维护每个字符在哪些位置上出现过，记 $i$ 字符出现在 $b_{i}$ 集合的位置，现有匹配串 $st$ ，维护当前仍然合法的起始点集合 $pos$ ，则有 $pos=pos \land (b_{st_i}>>i)$ 。

讲完了就好说了，强两个操作显然可以用位运算暴力，第二个就用我们上面的操作，时间复杂度是 $O(\dfrac{nT}{w}+\dfrac{nl}{w})$ 其中 $l=\max\limits_{i} \operatorname{len}(z_{i})$ 。

轻松最优解第二位，不知道第一位如何做到？

5. 与莫队结合

bitset 常用于常规数据结构难以维护的的判定、统计问题，而莫队可以维护常规数据结构难以维护的区间信息。把两者结合起来使用可以同时利用两者的优势。

P5355 [Ynoi Easy Round 2017] 由乃的玉米田

bitset 神秘密！

首先飞一个莫队上去，考虑加法操作如何解决，显然只要存在 $x+y=k$ 即可满足，而题目只要求可行性而非要求个数，故考虑 bitset 维护值域数是否出现，那么加法操作就是 (s1&(s1<<qry[i].x)).any()，其中 $s1$ 表示值域维护。

然后考虑减法，显然减法可以维护一个 $10^5 -x$ 的 bitset，设为 $s2$ ，那么判断方法就是：(s1&(s2>>(1e5-qry[i].x))).any()。然后考虑乘法，枚举约数 $O(n\sqrt{n})$ 做。问题在于除法很难维护，考虑根号分治， $>\sqrt{n}$ 的暴力找。但是问题在于 $\le \sqrt{n}$ 怎么做？

先将询问按左端点降序排列。然后取一个指针，一开始指向 $n$ 。若当前询问的左端点为 $l$ ，则将 $[l,j]$ 上所有元素的贡献插入树状数组中，并使 $j=l-1$ ，完成后直接在树状数组上获取当前询问的答案，时间复杂度 $O(n \sqrt{\max_i a_i}\log n )$ ，直接做即可。