摘要：
1.支配树问题 对于一张有向图，定义一个起点 \(S\)，若删去一个点 \(u\),则使起点 \(S\) 不可到达 \(v\)，则称为 \(u\) 支配 \(v\)。 性质1：显然有若 \(u\) 支配 \(v\)，\(v\) 支配 \(w\)，则有 \(u\) 支配 \(w\)。 性质2：每个点的 阅读全文
posted @ 2025-07-25 14:34
cinccout
阅读(89)
评论(0)
推荐(0)
摘要：
Burnside引理用于解决等价类数量问题。 1.置换 将有某种顺序的集合里的元素交换顺序的运算为置换，例如 \((a,b,c,d)\) 经过 \(\begin{pmatrix}1,2,3,4\\2,3,4,1\end{pmatrix}\) 这个置换后就会变成 \((b,c,d,a)\) 。 容易知 阅读全文
posted @ 2025-07-25 14:31
cinccout
阅读(108)
评论(0)
推荐(0)
摘要：
1.行列式求值 对于一个排列 \(p\) ，设 \(\tau(p)\) 为排列的逆序对数，则对于一个 \(n\times n\) 的矩阵 \(A\) ，定义它的行列式 \(\det(A)\) 为 \[\det(A)=\sum_{p} (-1)^{\tau(p)} \prod_{i=1}^n a_{i 阅读全文
posted @ 2025-07-25 14:27
cinccout
阅读(46)
评论(0)
推荐(0)
摘要：
就是求将字符串划分为若干回文子串的方案数。 1.回文后缀与border 首先，回文串的回文后缀集合与 border 集合完全相等，由回文串的定义可得。于是，border 的性质可以在回文后缀中使用，比如定理：将字符串的所有 border 的长度排序后，可以分割为 \(O(\log)\) 个等差数列子 阅读全文
posted @ 2025-07-25 14:16
cinccout
阅读(58)
评论(0)
推荐(0)
摘要：
1.第K大问题 给定 \(n\) 个集合，每个集合选择一个数，问所有方案中选择的数的和第K大的是多少，\(\sum |S|\leq 1e5,k\leq 1e5\) 。 考虑和最大的选择状态，一定是每个集合中选择最大的值，第二大的一定是将某个集合选择最大值改为选择次大值，不难发现对于每个状态后继状态都 阅读全文
posted @ 2025-07-25 14:15
cinccout
阅读(31)
评论(0)
推荐(0)
摘要：
此博客不是讲解用，是口胡用！ 多项式复合 用途是求多项式复合逆。若 \(F(G(x))=x\) 则 \(G(F(x))=x\)，因为若设左逆元 \(L(F(x))=x\)，右逆元 \(F(R(x))=x\) 则 \(L(F(R(x)))=L(x)=R(x)\)。于是称 \(F\) 为 \(L\) 的 阅读全文
posted @ 2025-07-25 14:12
cinccout
阅读(30)
评论(0)
推荐(0)
摘要：
此博客不是讲解用，是口胡用！ 特征多项式 矩阵 \(A\) 的特征多项式为 \(g_A(\lambda)=\det(\lambda I-A)\) 相似矩阵 若 \(B=PAP^{-1}\)，则 \(B\) 是 \(A\) 的一个相似矩阵，由于 \(\det\) 有乘法分配律，\(\det(A)=\d 阅读全文
posted @ 2025-07-25 14:11
cinccout
阅读(106)
评论(0)
推荐(0)
摘要：
1、全局最小割 有正权无向图当中，若边集 \(C\) 使得 \(\{V,E\backslash C\}\) 不连通，则称 \(C\) 为原图的割，求原图的最小割。这个问题等价于将原图染色为两个点集，两端颜色不同的边的边权之和。 考虑我们可以在多项式复杂度内解决 \(S-T\) 最小割。事实上原图中的 阅读全文
posted @ 2025-07-25 14:10
cinccout
阅读(34)
评论(0)
推荐(0)
摘要：
1.使用SG函数 首先假设一个局面的 \(SG\) 函数值是所有奇数层石子数异或起来。 这样只需要证明一个状态是所有后继的 \(mex\)，换句话说证明两点：一个状态不可达它自己；一个状态的后继的 \(SG\) 函数值包含所有比它小的自然数。 一个状态肯定不可达它自己，因为操作是减少一堆的石子数，或 阅读全文
posted @ 2025-07-25 14:09
cinccout
阅读(27)
评论(0)
推荐(0)
摘要： 
此篇为不会分析LCT复杂度，忿忿而做。 势能分析 对于一个数据结构，若每次操作的复杂度和某个量相关，可以设它为势能函数 \(\phi\) 进行分析。 接着对于每一次操作 \(x\)，设时间代价为 \(T_i\)，势能变化量为 \(\Delta\phi_i\)，令 \(A_i=T_i+\Delta\p 阅读全文
此篇为不会分析LCT复杂度，忿忿而做。 势能分析 对于一个数据结构，若每次操作的复杂度和某个量相关，可以设它为势能函数 \(\phi\) 进行分析。 接着对于每一次操作 \(x\)，设时间代价为 \(T_i\)，势能变化量为 \(\Delta\phi_i\)，令 \(A_i=T_i+\Delta\p 阅读全文
posted @ 2025-07-25 14:07
cinccout
阅读(49)
评论(0)
推荐(0)
浙公网安备 33010602011771号