文章

什么是 2-SAT？ SAT 是适定性（Satisfiability）问题的简称。一般形式为 k – 适定性问题，简称 k-SAT。而当 $k > 2$ 时该问题为 NP 完全的。所以我们只研究 $k = 2$ 的情况。 简单来说的话就是有 $n$个变量 $x _ 1, x _ 2, x 阅读更多…

这个问题困扰我很久了，一直觉得没太大关系就没解决，今天终于忍不住解决了 解决方法很简单，Ubuntu 的中文系统字体是 Noto Sans CJK SC（网上那些说是文泉驿的，该去看眼科了）因此打开 Typora 使用的主题的.css 文件，Ctrl + F 找到所有的 font-family，然 阅读更多…

拉格朗日反演 如果对于幂级数 $F(x)$和 $G(x)$，有 $G(F(x))=F(G(x))=x$，则称 $F(x)$和 $G(x)$互为复合逆。记 $[x^i]F(x)$为 $F(x)$的 $i$次项系数，以此类推，对于这样的 $F(x)$和 $G(x)$，有： $$[x^n]G(x)=\fr 阅读更多…

莫队 $+$ $bitset$. 我们可以用 $bitset$ 维护当前 $l,r$ 区间数的出现的状态，莫对依旧按照套路搞，然后来考虑怎么回答每一个询问。 对于操做 $1$ ，要求回答我们从当前区间能否找出 $a,b$ 使得其差为 $x$。 很显然，$a-b=x$ 等价于 $a=b+x$。 我们维 阅读更多…

为了证明过年的时候 $MiNa$ 还是有人的本蒟蒻特来水一波…… 其实很短的啦，感觉…… 感觉淀粉质这种东西好像没什么可以总结的…… 只会有一些简单的板子题而已……(实际上是砍不动难的题目) (淀粉质吗？ 阅读更多…

第一类斯特林数的一种 $O(n\log n)$倍增求法 摘要 本文介绍了一种可以 $O(n\log n)$求出第一类斯特林数 $S_n^1,S_n^2\cdots,S_n^n$的方法。 什么是第一类斯特林数 第一类斯特林数 $S_n^m$是将 $n$个元素划分为 $m$个圆排列的方案数。 圆排列：将 阅读更多…

数树 题意： U 为所有 $n$个点的树的集合 对于给定的两棵树 $S, T$, 定义 $F(S, T) = y^{公共的边数}$ Question1：给定 $n, S$，求 $\sum_{T\in U}F(S, T)$ Question2：给定 $n$, 求 $\sum_{S \in U, T\i 阅读更多…

膜法森林 2333…… 显然是一道 $LCT$ 动态加边的题目。 然而并不需要这么高深的数据结构来动态加边 (实际上是不会)，我们只需要 $Spfa$ 动态加边即可切掉此题。 怎么 $Spfa$? 又是个怎么的动态加边法呢？ 在下面我先给出代码，然后再来一步一步剖析 (跟 $ 阅读更多…

1. 是什么 似乎很多地方直接管它叫 Pollard rho 算法 又名泼辣的肉算法 用于对 $n$进行质因数分解 根据生日悖论，复杂度大约是 $O(n ^ \frac 1 4)$的（算法导论中写的复杂度更准确，不过无伤大雅）2. 算法 假设我们要分解 $n$，那么首先 Miller-Rabin 阅读更多…

1. 是什么 用来在 $O(\log p)$的复杂度内检测 $p$是否为素数 是一种随机化玄学算法，不一定保证正确 正确率后面会讲 2. 算法 首先由费马小定理可知： 若 $p$为素数，那么对于任意一个 $a \in [1, p – 1]$都有： $$a ^ {p – 1} 阅读更多…