0x01位运算AcWing89.a^b快速幂模板题。令\(k\)为\(b\)在二进制下的位数，\(t_i\)为\(b\)在二进制下的第\(i\)位。则\(b=t_{k-1}{2^{k-1}}+t_{k-2}2^{k-2}+...+t_02_0\)于是\(a^b=a^{t_{k-1}{2^{k-1}}}*a^{t_{k-2}{2^{k-2}}}

0x21树与图的遍历164.可达性统计令\(f[x]\)表示从\(x\)出发可到达点的集合，那么\(f[x]=(\cupf[y])\cupx\)（存在边\((x,y)\)）。所以我们可以使用拓扑排序，倒着拓扑序进行计算。处理这个集合我们可以想到二进制压缩，但是一般二进制数没有这么大，所以需要\(bitset\)。bit

0x11栈栈的运用AcWing41.包含min函数的栈用一个辅助栈存所有可能成为答案的值，即维护两个栈，一个栈正常存，另一个栈存所有时刻的最小值。具体维护时如果新加入的值比辅助栈的栈顶小，就将它加入辅助栈，删除时判断两个栈栈顶是否相等，如果相等就让辅助栈栈顶出栈。classMinStack{

0x42树状数组何为树状数组？首先，树状数组是用来维护序列的前缀和的。其次，我们要知道树状数组是如何将大区间拆分成一堆小区间的。比如\(7=111_{(2)}\)，我们可以将其拆分为\([1,4],[5,6],[7,7]\)，再比如\(12=1100_{2}\)，我们可以将其拆分为\([1,8],[9,12]\)。所以对

Sudoku来自蓝书思路优化搜索顺序，位运算常数优化。优化搜索顺序数独问题的搜索很简单，“搜索状态”就是每个位置上填了什么数。在每个状态下，选择一个未填位置，检查那些填入仍能满足数独条件（合法）的数字。构成的新的局面即为该状态的“分支”。足够暴力的写法为依次对每个位置进

我们先不要管两个数按位与为\(1\)和两个数按位或为\(0\)的情况那么剩下的情况就是很简单的2-SAT问题就像并查集处理二元关系一样，这里最后建成的图一定是完全对称的，如下其中每个点都是一个SCC然后我们再来看剩下的两种情况，拿两个数按位与为\(1\)为例这就说明两个数必须要都是

详细阐述一下蓝书的做法首先，我们创造\(n\)个点，每个点有一个权值\(p_i\)，也有一个编号蓝书的连边就是对每一个点，从这个点出发连一条有向边到编号为这个点权值的点比如书上举的那个例子，编号分别为\(1,2,3,4,5,6\)，权值分别为\(2,4,6,1,5,3\)这样这个图肯定是由若干个环组成的然后

其实这个证明与前面那个证明很像假设最终生成的生成树不包含这\(m-k\)条边中连接生成森林的两个不连通节点的最小的边，那么我们从这些最小的边中任选一条边加入到树中会形成一个环，而且这个环（除了加入的这条最小边）一定存在一条边不是最开始的\(k\)条边中的某一条（因为如果这个环除了

这道题目真实绝了，这篇随笔主要是对蓝书上面的注释首先那个结论肯定要知道，然后选取\(1\)号点作为基准点也是想到了的那么接下来肯定就是把\(1\)号点所在连通块当做树根嘛，问题是怎么去分配剩下的点我最开始想的是像树形背包一样去DP，但是不知道具体有多少子树，然后我又想枚举子树个

这道题目二分的做法见蓝书介绍一个斜率优化的做法但是说实话，我是证明不了下面为啥直接取队头就可以解决问题了下面这张图片又在说什么。。。

最短Hamilton路径状压dp。设\(f_{S,i}\)表示走过的节点状态为\(S\)\((0\)为没走过，\(1\)为走过\()\)，当前在点\(i\)时的最小代价，显然\(S\)的第\(i\)位必须为\(1\)。那么\(f_{S,i}=\min_{S\operatorname{and}2^j=1,j\neqi}\lbracef_{S\operatorname{xor}