组合计数类
-
对于 \(\sum\limits_{k=1}^{m}{x_k} = n\) 的限制，在任何解中，本质不同的 \(x_k\) 的数目是 \(\mathrm{O}(n^{\frac{1}{2}})\)。
-
一道题目涉及到异或和的时候想想Kummer定理，\(\binom{n}{k}\ mod\ 2 = 1\iff k\subseteq n\)，这是Lucas定理的一个直接推论。
一个意义不明反演式
根据一些位运算运算律有：
\[\bigoplus\limits_{t\subseteq y\subseteq x}{((u-x)\oplus y)} = \begin{cases} u, &t=x\\ 0, &|t| < |x|-1\\ t\oplus x, &|t| = |x|-1 \end{cases} \]可以用于反演 \(B_i = \bigoplus\limits_{j\& i = j}{b_j}\)：
\[\begin{align*} b'_i &= \bigoplus\limits_{j \subseteq i}{((u - i) \oplus j)\&B_j}\\ &= \bigoplus\limits_{j \subseteq i}{\left[((u - i) \oplus j)\&\bigoplus\limits_{t\subseteq j}{b_t}\right]}\\ &= \bigoplus\limits_{t \subseteq i}{\left[b_t\&\bigoplus\limits_{t\subseteq j\subseteq i}{((u - i) \oplus j)}\right]}\\ &= b_i\oplus\left(\bigoplus\limits_{k=0}^{|u|}{2^k\&i\&b_{i-2^k}}\right) \end{align*} \]当然这用二项式反演直接也能做。目前没有已知的其他应用。
数论类
-
处理取模：\(x\ mod\ p = x - p\lfloor\frac{x}{p}\rfloor\)。
-
处理 \(-1\) 的幂：\((-1) ^ a = 1 - 2(a\ mod\ 2) = 1 - 2(a - 2\lfloor \frac{a}{2}\rfloor)\)，从而把 \(a\) 从指数上拿下来。
-
处理求和式：交换求和顺序，如果不能交换，考虑凭空求和：\(x = \sum\limits_{0}^{x-1}1\)。
-
处理有关上下取整的限制：\(x\le \lfloor y\rfloor\iff x\le y\)，\(x \ge\lceil y\rceil\iff x\ge y\)，反之亦然，可以这样把取整符号里的除法、根号等去掉然后再把取整加回去。
-
\([x = 1]\) 考虑凭空莫反转化成 \(\sum\limits_{d | x}\mu(d)\)；\([\gcd(x, y) = d]\) 考虑枚举 \(d\)，使得 \(Xd = x, Yd = y\)，然后变成 \([\gcd(X, Y) = 1]\)，用凭空莫反。
-
某个数与另一个数互质，可以考虑转化为模另一个数的所有质因子都不为0。当然也可以考虑莫反，这两者其实差不多。
杂项结论类
-
某个集合中字典序最小的置换，满足它的逆置换倒过来形成的串的字典序，在同一个集合的逆置换倒序集合中，字典序最大。（贪心的时候，优先把大的数放在最后面，和优先让前面数最小一样，都可以得出最小字典序）
-
考虑一个序列a，满足它的和为1，则它的所有循环同构串互不相同，且其中恰好有一个满足其所有部分和为正。（Raney引理，出自《混凝土数学》）