省选一轮

拉格朗日差值
最小树形图
二项式反演
BSGS
最小割树
虚树
boruvka

\(1.0/1\)串也可以黑白染色。

\(2.\) 在平面图中,总是满足: \(V-E+F=1+C\)(\(F\)是面数,\(C\)是联通块数)。

\(3.S\bigcap T = \emptyset\Leftrightarrow S\subseteq \complement_uT\)

\(4.\)差分表第\(0\)条对角线为\(c_1,c_2,c_3,\cdots c_k,0,0,\cdots\),那么通项为\(h_n=\sum_{i=0}^k c_i{n\choose i}\), 前缀和为\(\sum_{i=1}^nh_i=\sum_{i=1}^n\sum_{j=0}^kc_j{i\choose j}=\sum_{j=0}^kc_j\sum_{i=1}^n{i\choose j}=\sum_{j=0}^kc_j{n + 1\choose j + 1}\)

\(5.\)点分治处理联通块问题:强制每次都经过分治中心。

\(6.\Theta(1)\)快速乘:$a % p = a - \lfloor \frac a p \rfloor\times p $

\(7.\)通过交换对\(0/1\)序列排序:倍增法。

\(8.\)矩阵树定理。

\(9.\)全幺模矩阵:只有\(0,1,-1\);每列至多两个非零数;如果一列包含两个非零数,他们相同则这两行不在一个集合,不同则在一个集合,最后可以划分成两个合法的行集合。这样的矩阵经过初等变换还是全幺模矩阵。

\(10.\sum_{i=1}^n\lfloor\frac n i\rfloor = \sum_{i=1}^n \sigma(i)\)

\(11.\sum_{gcd(i,n)=1}i=\frac{\varphi(n)n}2\)

\(12.\varphi(n)=n\prod_{p|n,p~is~prime}\frac{p-1}p\)

\(13.\) 当 \(F(x)\)是二次函数,\(\int F(x)=\frac{(r-l)}{6}[F(r)+F(l)+4F(\frac{l+r}2)]\)

\(14.\)在\(\%p\)意义下,\(1-p-1\)逆元互不相同。

\(15.\) 与 \(n\)互质的数每\(n\)个一循环,\(\gcd(i,n)=1\Leftrightarrow\gcd(i+n,n)=1\)

\(16.(x+1)^p=x^p+1\)

\(17.\mu^2(i)=\sum_{d^2|i}\mu(d)\)

\(18.\)两个不同的数的\(\gcd\)不会超过两个数的差。

\(19.\)在\(xor\)意义下,所有环都可以被简单环(dfs树上的非树边或dfs不走当前栈上的点)组成。

\(20.\)两棵树相连,新树重心在原来两个重心之间的路径上。

\(21.\)一棵树加/删一个点,重心只移动一条边。

\(22.\gcd(i,j)=\sum_{d|\gcd(i,j)}\varphi(d)\)

\(23.I[\gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)\)

\(24.\)对于询问修改等操作分块,平均复杂度。

\(25.\)在dfs序上建主席树,解决子树/链问题。

\(26.beatty\)数列。

\(27.x^k=\sum_{i=0}^{x~or~k}{x\choose i}i!S_2(k,i)\)

\(28.\)已知\(ab/ba,bc/cb\) 可以得到 \(ac\),这样的问题有传递性,考虑最小生成树。

\(29.xy\)是完全平方数,\(yz\)是完全平方数,那么\(xz\)也是完全平方数。

\(30.\)图的最短路图也是DAG,DAG求割边当无向图做。

\(31.\)子树在\(dfs\)序/括号序中代表一段区间。

\(32.\)拓扑图统计路径的方法:把图断成两部分,只有左部向右部的连边,路径分三种:左部自己的,右部自己的,跨过断层的。

\(33.\)用当前图案为单位拼基础图案\(\Leftrightarrow\)用基础图案代替每个单位。

\(34.\)在\(\%2\)意义下,\(+-\)都变成\(xor\)。

\(35.n\)个点的虚树,按照\(dfs\)序排序,边数\(=\frac{\sum_idis(p_i,p_{i\%n+1})}{2}\)

\(36.\)一个排列可以看成是一个置换,\(i->p_i\)连边,\(p_{p_i}\)就是走两步,结果奇环改变顺序,偶环变成两个。

\(37.g\)存在条件:\(p=q^a,2q^a,2,4\)(\(q\)是奇素数);\(\forall p_i,g^{\frac{\varphi(p)}{p_i}}\ne 1(mod~p)\)

上一篇:洛谷 - P2568 - GCD - 欧拉函数


下一篇:计算Grassmannian geodesic