Colythme

树上莫队首先有一道题 王室联邦题目大意给定一棵树，将树分为大小范围为 $[B, 3B]$ 的连通块集，求方案 树上分块方法之一类似贪心，用栈维护还没有在连通块中的子节点，对于递归到的当前的点 $p$ ，扫描它的子树，能拼凑就拼凑 但是注意最后可能还会有一些点（一定包括根）剩下，那么将这些点并到最后一个连通块即可 显然每个连通块都满足大小为 $[B, 3B]$ 核心代码123456789101112131415void DFS (int root, int father) { int bot = top; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; if (v == father) continue; DFS (v, root); if (top - bot >= B) { capt[++ bind] = root; while ...

前置相关 类型积性函数（注：以下皆为完全积性函数，即无需满足 $x \perp y$ 即有 $f(x) · f(y) = f(xy)$ $\epsilon (n) = [n = 1]$ $id (n) = n$ 狄利克雷卷积与莫比乌斯函数 狄利克雷卷积与欧拉函数 此处若以 $id $ 作单位元，则 $1$ 为 $\phi$ 的逆，即 $\phi * 1 = id$ 证明：由 $\sum\limits_{d | n} \phi (d) = n$ ，再带回原式可证 莫比乌斯函数与欧拉函数的转化$$\begin{aligned} \phi * 1 &= id \ \phi * 1 * \mu &= id * \mu \ \phi * \epsilon &= id * \mu \ \phi &= \sum\limits_{d | n} \mu(d) \frac{n}{d} \ \frac{\phi}{n} &= \sum\limits_{d | n} \frac{\mu(d)}{d} \end{aligned}$$ 杜教筛 杜教筛用于求解积性函 ...

处理问题$$C_i = \sum\limits_{i \oplus j} A_iB_j$$ 离散沃尔什变换「DWT」设 $DWT_i (A) = \sum\limits_{j = 0}^n A_jf(i, j)$ （第一次知道原来离散变换是这么设的） 又由于$$\begin{aligned}DWT_i(A)DWT_i(B) &= DWT_i(C) \\\sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j)f(i, k) &= \sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j \oplus k)\end{aligned}$$故 $f(i, j)f(i, k) = f(i, j \oplus k)​$ 于是就有一些结论 $and: f(i, j) = [(i and j) = i]$ $or: f(i, j) = [(i and j) = j]$ $xor: f(i, j) = (- ...

前置知识多项式除法|取模该部分见 多项式操作 特征值与特征向量（这部分我也不怎么理解，就大概记个结论） 对 $n$ 阶矩阵 $A$ 的特征向量 $\vec{v}$ 与，有特征值 $\lambda$ 满足$$A\vec v = \lambda\vec v$$移项则有 $(\lambda I - A)\vec v = 0$，其中 $I$ 为单位矩阵 那么有解的充要条件是 $det(\lambda I - A) = 0$ 令 $f(\lambda) = det(\lambda I - A)$，即此时可将 $det (\lambda I - A)$ 看作一个 $n$ 阶多项式，则称 $f(\lambda)$ 为矩阵 $A$ 的特征多项式，对矩阵 $A$，其任意特征值 $\lambda_0$ 都满足 $f(\lambda_0) = 0$ $\text{Hamiton-Cayley}$定理对矩阵 $A$ 及其特征多项式 $f(x)$，满足 $f(A) = O$，其中 $O$ 为零矩阵 证明留坑 常系数齐次线性递推求一个满足 $k$ 阶齐次线性递推数列 $h_i$ 的第 $n$ 项，即$$h_n = ...

显然答案是总哈密顿回路数除以值得记录的竞赛图数 那么先求解总哈密顿回路数，考虑每个哈密顿回路会在几个值得记录的竞赛图中，则有$$Hamitons = (n - 1)!2^{C_n^2 - n}$$即总共有 $(n - 1)!$ 种哈密顿回路，然后剩下的边随便选 于是现在考虑值得记录的竞赛图数 首先如果一个竞赛图要有哈密顿回路，那么它至少要有一个包含所有节点的环，即该图是强连通的，并且显然非强连通竞赛图它一定不存在哈密顿回路，所以有结论 有且仅有强连通竞赛图存在哈密顿回路 那么问题转化为求解强连通竞赛图 发现正面难以求解，就考虑反面求解 设 $f_n$ 表示 $n$ 个节点的强连通竞赛图数，$g_n$ 表示 $n$ 个节点的竞赛图数（即 $2^{C_n^2}$），可得 $DP$ 方程$$f_n = g_n - \sum\limits_{j = 1}^{n - 1} f_jg_{n - j}\dbinom{n}{j}$$其中求解非强连通竞赛图部分是每次将拓扑序最小的强连通分量提取出来计数，那么剩下的点随意连接（注意，此时取的是拓扑序最小的强联通分量，故该强联通分量与其它连通分量的连边方 ...

导数平均变化率函数 $y = f(x)$ 从 $x_1$ 到 $x_2$ 的平均变化率为 $\frac{f(x_2) - f(x_1)}{x_2 - x_1}$，简记作 $\frac{\Delta y}{\Delta x}$ 瞬时变化率与导数函数 $y = f(x)$ 在 $x = x_0$ 处的瞬时变化率是函数 $f(x)$ 从 $x_0$ 到 $x_0 + \Delta x$ 的平均变化率在 $\Delta x \to 0$ 时的极限，记作 $\lim_{\Delta x \to 0} \frac{f(x_0 + \Delta x) - f(x)}{\Delta x} = \lim_{\Delta x \to 0} \frac{\Delta y}{\Delta x}$ 一般地，我们称上文的瞬时变化率为函数 $y = f(x)$ 在 $x = x_0$ 处的导数，记作 $f’(x_0)$ 或 $\frac{\mathrm{d} y}{\mathrm{d} x} \bigg|_{x = x_0}$ 实际上，导数描述的即为任何事物的瞬时变化率 Example： 求 $y = f(x) = ...

后缀数组在文本串中寻找子串在文本串 $T$ 中寻找模式串 $S$，那么 $S$ 一定是 $T$ 的某个后缀的前缀，后缀排序后，在 $SA$ 中二分 $S$ 的位置，每次 $check$ 比较时间 $O (|S|)$，总时间复杂度 $O (|S| \log |T|)$ 比较两个子串的大小关系比较 $S$ 的子串 $A = S[l_1…r_1], B = S[l_2…r_2]$ 的大小关系 若 $lcp (l_1, l_2) \ge \min (|A|, |B|)$，则 $A < B \Longleftrightarrow |A| < |B|$，反之 $A < B \Longleftrightarrow rk_{l_1} < rk_{l_2}$ 本质不同子串数目设字符串 $S$ 长度为 $n$ $ans = \frac{n(n + 1)}2 - \sum\limits_{i = 2}^n height[i]$ 从字符串首或尾取字符构成最小字典序的字符串[USACO07DEC]Best Cow Line G 最基本贪心，若两端字符不同，优先取大的，那么问题就在于两端相 ...

首先定义多项式的度数 $degA$ 为多项式 $A(x)$ 的最高次数 那么多项式 $A(x)$ 的逆即为存在多项式 $B(x)$ 使得条件满足：$$A(x)B(x) \equiv 1 \pmod{x^n}$$ 求解过程分治 $FFT$对 $A(x) = \sum\limits_{k = 0}^{n - 1} a_kx^k, B(x) = \sum\limits_{k = 0}^{n - 1} b_kx^k$ 从常数项考虑，有 $b_0 = \frac1{a_0}$，则由 $\sum\limits_{k = 0}^n b_ka_{n - k} = 0$ 可得$$b_k = \sum\limits_{i = 0}^{k - 1} b_i\left(- \frac{a_{k - i}}{a_0}\right)$$ 倍增迭代假设存在多项式 $A(x)$ ，以及其逆 $B(x)$ 满足条件 ，那么必定有$A(x)B(x) \equiv 1 \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} … (1)$ ，因为 $x^n$ 是 $x^{\left\l ...

多项式求逆该部分见 多项式求逆 多项式除法|取模有 $F(x) = G(x)Q(x) + R(x)$，给定 $F(x)$ 与 $G(x)$，求解 $Q(x), R(x)$，其中 $F(x), G(x)$ 最高次数分别为 $n, m$ 显然地，$Q(x), R(x)$ 的最高次数必定不超过 $n - m, m - 1$，考虑式子变形$$\begin{aligned}&F(x) = G(x)Q(x) + R(x) \\\Rightarrow &F(\frac1x) = G(\frac1x)Q(\frac1x) + R(\frac1x) \\\Rightarrow &x^nF(\frac1x) = x^mG(\frac1x)x^{n - m}Q(\frac1x) + x^{n - m + 1}x^{m - 1}R(\frac1x) \\\end{aligned}$$令 $A_R(x)$ 表示 $A(x)$ 系数翻转后得到的多项式，即 $A(x)$ 系数 $(a_0, a_1, …, a_n)$，$A_R(x)$ 系数 $(a_n, a_{n - 1}, …, a_1) ...

题目描述有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。$1$ 号站在原点，$i$ 号 $(1 \le i \le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1 = 0$，$X_1, X_2, …, X_N$ 单调递增（可能有人位置重叠）开始时，$K$ 号的烟花刚开始燃烧，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数 数据范围对 $100\%$ 的数据，$1 \le K, N \le 10^5, ~ 1 \le T \le 10^9, ~ 0 \le X_i \le 10^9, ~ X_1 = 0$ 题解很显然所有人一定会不断向拿烟花的人靠近 可以发现，一个拿烟花棒的人和另一个人相遇时，让另一个人跟着拿烟花的人走直至烟花在灭掉的瞬间将烟花传递的情况和在相遇时传递时一样的（注意相对位置， ...