超神建图技巧合集
每个骨牌变成让空位移动的至多两条有向边，证明图中无环，形成森林。
然后黑白染色，两类森林互不影响。转为每次标记 A 类一棵子树与 B 类一棵子树形成的所有点对。
再转化，子树 -> 欧拉序列，变为矩阵交，线段树搞定。
0 为右走一步，1 为左走一步，操作即为将一段回路反着走。
可猜想证明导出的无向图的任意一条欧拉路径均合法。
字典序最小的欧拉路径用贪心。本题中可以记录一个点左边的边全部被访问判断是否可以向右走。
转化为每次删掉一些基环树中所有的环，然后将失去出边的点重新指向下一个点。然后分层 dp。
在数轴上的建图，在模的意义下求最短路。
Pollar-Rho 很好用，但是一定要特判掉边界情况啊啊啊啊。。。（我的 Pr 在 n=4 时会死循环）
利用强连通分量的性质就是了，没什么好说的（
注意遍历补图 $k$ 条边的时间复杂度为 $O(m+k)$ （$m$ 为原图边数）。
1. 莫比乌斯反演可以迅速求出一个数列中与某一个数互质的数个数
2. $10^7$ 内的数质因子实测最多有 $448$ 个hh
3. $O(n \log n)$ 筛出 $10^7$ 内所有数的因数只需要约 1.5s
4. 建图技巧：取补图。 题目中原来是要 “不互素连边，求 团 或 无 n-1 度点” ，变为 “互素连边，求 独立集 或 无孤立点”，easy~
没什么，注意有时候说“最少进行多少次”，有时候可能是仔细思考，分析性质，只需要1~2次。。。
特别是像这道题，说“最少进行多少次”，还要算出“有多少种方案取到最小值”。。。
一个很厉害的技巧：凭空将无向图拆点为二分图。
不要问为什么，想到就行了（
然后，一个点可以根据度数拆成多个点。
然后这道题就成了：给定一个二分图，其中点的最大度数为 $k$，求一种边染 $k$ 色的方案，使得每个点出发的边颜色各不相同。
无脑增广：每次新加一条边 $(x,y)$，如果有一种颜色可以同时满足 x 和 y 就直接加入。
否则设 x 的一种合法颜色是 1，y 的一种合法颜色是2。