2-Spin System Quick Notes
SettingConfiguration : A configuration of graph is a map such as:
\begin{aligned}
\sigma: V &\to 2^V\\
u&\mapsto \{+,-\}
\end{aligned}Partition Function: For graph , define its partition function as
Z_G(\beta, \gamma, \lambda) = \sum_{\sigma} \beta^{m_{++}}\gamma^{m_{--}}\lambda^{n_+}where is the number of edges between two vertices pinned to , is the number of vertices pinned to , and we sum over all possible configurations.
Initially, we wonder when there exsits a polynomial time ...
浅谈 SAT 问题与 SAT-Solver
通过 Hackergame 比赛滑水知道了有 SAT-Solver 这个东西（其实是先知道了 SMT-Solver 然后再知道了 SAT-Solver），遂花了点时间去研究了一下。
这篇文章的前半部分是 SAT 相关的一些常识的回顾，后半部分开始介绍求解一般 SAT 问题的算法。
笔者计划在24春系统学习形式化方法入门内容，在那之后会进一步整理更多内容。
SAT 备件简述SAT 问题与 CNF 格式SAT 问题即可满足性问题 (Satisfiability Problem)：一般被定义为布尔可满足行问题或命题可满足性问题，即：
布尔可满足性问题 (Boolean Satisfiability Problem) ：给定布尔表达式 (由 AND, OR, NOT, 变量, 和括号构成), 是否存在对变量 TRUE 或 FALSE 的赋值, 使得整个表达式真。例如
(x + y\neg z)(x + y + z)(\neg y + \neg z)
以及：
命题可满足性问题 (Propositional satisfiability problem) :给定命题逻辑公式, 命题是否可满 ...
Dancing Links X 算法学习笔记
在 Hackergame 赛后自己去补了点基础，现在写一点 Dancing Links X 算法的学习笔记
算法原理算法原理参见 Dancing Links - OI Wiki 。
这个算法的原理已经在各种文章中被重述了 114514 次，我并没有信心讲得比他们好，不过还是简要描述一下。
代码实现代码内包含大量注释（代码基本就是 OI Wiki 的）
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485struct DLX { static const int MAXSIZE = 1e5 + 10; int n, m, tot, first[MAXSIZE + 10], siz[MAXSIZE + 10]; int L[MAXSIZE + 10], R[MAXSIZE + 10], U[MAXSIZ ...
子群格基本算法
子群格基本算法子群格与子群层级
定义 一个群的子群格是由其所有子群和子群间的包含关系构成的二元组
实际上就是子群所构成的偏序集
定义 子群格中的元素地层数 定义为子群阶数中素因子指数的和
于是我们自然地想到，可以按照层数以此构造出一个群的全体子群
循环扩张基础算法 是一个 层的子群的一个充分不必要条件是存在一个 层子群 和一个元素 使得
使用这种方法我们可以从由一层的子群构造出下一层的子群（注意到这个方法并不永远能构造出全部的子群，在一个群没有完全子群的情况下这是可以的）
接下来遇到的一个问题是，如何保证加入第 层的子群与之前的子群不重合呢？
事实上会发生重合的情况只有以下两种
是第 层子群中的元素
是已经加入第 层的子群中的元素
于是我们给出一个简单的算法
算法 1
12345678910111213for U_{i-1} in the layer[i-1]: Gamma := G - U_{i-1} for W in the layer[i]: if U_{i-1} is contained in W: Gamma -= W whi ...