说实话这个东西其实挺有趣的。 证明的话其实我不是很会，貌似是用矩阵证明是一个范德蒙德矩阵是有唯一解的。 我们直接举例子来说吧。 $f(n) = f(n - 1) + f(n - 2)$。 设 $F(z) = \sum_{i = 1}^{\infty} f(i) z^i$，显然存在这样的方程满足。 $$F(z)z^2 = F(z)z + F(z)$$那么我们将其移项可以得到： $$F(z)(z^2 - z - 1) = 0$$显然 $F(z)$ 不为 $0$，那么我们让后面的那个东西 $= 0$。其实后面的柿子就是特征方程。 我们容易解出两个解 $z = \frac{1 \pm \sqrt 5}{2}$。 得到 $f(n) = Ax_1^n + Bx_2^n$ 我们带入前面的两个值 $f(1) = f(2) = 1$ 得到 $A = \frac{1}{\sqrt 5}, B = - \frac{1}{\sqrt 5}$ 可以求出通项。 $$f(n) = \frac{\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 - \sqr ...

emmm，先说明一下，作者其实不是很会，有些问题请指出。 $\color{red}\tt \text{定义}$ $\Theta(f(n))$ 表示时间复杂度渐进的上下界。 $\Omega(f(n))$ 表示时间复杂度的下界。 $O(f(n))$ 表示时间复杂度的上界。 $\color{red}\tt Master\ Theorem$ 设递推式 $T(n) = aT\left(\dfrac{n}{b}\right) + f(n)$。 设常数 $\epsilon > 0, k \ge 0$， $$T(n) =\begin{cases}\Theta(n^{\log_ba}), f(n) = O(n^{\log_ba - \epsilon}) \\Theta(f(n)), f(n) = O(n^{\log_ba + \epsilon}) \\Theta(n^{\log_ba}\log^{k + 1}n), f(n) = O(n^{\log_ba} \log^kn)\end{cases}$$ 也就是考虑递归的时候相邻两层之间的公比，我们是取分子分母中比较大的那个，特殊的情况就是公比 ...

CF757G Can Bash Save the Day? 时间复杂度分析好题（大雾）。 将询问拆成几部分，也就是 $dis(u, v) = dep(u) + dep(v) - 2 * dep(Lca(u, v))$。 显然对于 $Lca$ 我们直接进行树链剖分即可。 我们对于每一个 $v$ 维护 $\le l$ 的 $dep(Lca)$ 的贡献，为了节省空间我们直接使用可持久化线段树，进行插入的时候使用标记永久化。 具体来说就是将 $[l, r]$ 这个 $dfs$ 序的区间进行 $+ 1$ 意味着，整个区间加上了 $sumdep_r - sumdep_{l - 1}$ 的贡献，之后为了保证线段树的复杂度是 $\log n$ 我们直接在这里记录标记了几次。然后在进行查询的时候直接下传还有多少次标记没有传完即可。直接像普通线段树下传标记会出现下传了不是属于当前线段树节点的情况。 对于修改的话，发现前缀和只有一个位置变了，也就是只需要修改一个位置。 然后因为本题是卡空间的，我们考虑一次加入点是 $\log n$ 的，一次插入也是 $\log n$ 的，本质就是一次插入需要 $\log^ ...

CF827F Dirty Arkady’s Kitchen 说实话这个拆点和拆边都是可以过的。 发现边是可以重复经过的，那么对于两条边只要考虑奇偶性就好了。 我们考虑对于一条边拆成两部分，一个是起点为奇的，另外一个是偶的。 什么时候一条路径是合法的，也就是说对于一条边 $E$，起点到他的路径上肯定存在一条边的上界是 $\ge E_l$ 的。 注意这里边是会消失的。 然后考虑加边的顺序，比较显然直接是从小到大进行加边。这样对于我们路径的上界肯定是从拓扑序比起小的边得到的，也就是意味着这条边出现的时候肯定是可以走的。 设 $f(i, 0/1)$ 表示到当前点的奇偶性为 $0/1$ 的最晚时间。 如果说当前时刻这条边是不能走的，我们可以考虑将其加入到当前 $u$ 的边集中，之后更新。 因为现在不能走并不意味着不能被其他的边更新。 然后之后更新就是像最短路一样，如果说一条边的终止点在之前被更新过了，那么我们就直接跳过更新。 123456789101112131415161718192021222324252627282930313233343536373839404142434445 ...

CF1523H首先这个东西很像一个 $dp$。我们不妨将删点记录成一个状态，然后发现状态数量太多了，我们可以倍增优化一下状态数量。 设 $f(i, j, k)$ 表示从点 $k$ 开始删除了 $j$ 个点，走 $2^i$ 个点能到达的最优的点。 我们考虑最简单的情况，就是从 $i$ 开始走 $j$ 步能走到的最优的点。答案是 $x +a_x$ 最大的点，因为对于一个 $y > x, a_y + y < a_x + x$ 这样就可以走更多的点。 我们通过 $st$ 表的方式直接进行维护即可。 对于一个询问，我们对于二进制进行拆位分析即可，对于一个不能直接到达的加上 $2^i$ 的贡献。注意特判直接能到达的情况和走一步能到达的情况。 $2^0, 0$。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 ...

CF1446D2 Frequency Problem (Hard Version)讲一种 $O(n)$ 的神仙做法，代码转载于 $gmh77$ 神仙。 说实话这个我也不懂算不算转载，如果有问题可以直接私聊我。 考虑对于最终答案来说，我们重复计算不符合条件的比较小的区间是不影响的。 所以我们可以考虑对于每一个非众数进行计算。 计算只有一个众数的情况 虽然说可能出现了两个非众数，但是肯定存在比其更大的区间。 计算多个众数的情况，我们不妨记录一下众数的位置每次来跳众数，每一次更新一下当前值为 $s$ 的非众数的出现次数。也就是从左到右进行枚举。 考虑对于非众数进行圈定一个区间，同时记录当前值 $s$ 出现的最靠右的位置和其经过的众数，为了防止数组冲突可能需要额外处理一下。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818 ...

平面图转对偶图[BeiJing2006]狼抓兔子这个是经典题，显然就是求一个最小割。然后网络流建立无向图即可。 但是如果数据范围没有那么小呢？ 众所周知网络流的复杂度其实挺玄学的，而且这又是一张平面图，不妨将其转化为对偶图。 定义： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146> ```面的次数```：边界的长度，用 $deg(R_i)$ 表示。>> ```阶` ...

CF756F 原本以为校内有神仙要讲评这题，就赶快去做了。结果啊，是我题号记错的 $\dots$ 题目大意： 给出一个字符串请解析这个字符串构成的数。 $l - r$ 表示 $l \sim r$ 中的所有数， $8 -10$ 表示 $8910$。 $+ x$ 表示单纯增加一个 $x$，如 $8-10+5$ 表示 $89105$。 我们称上面的这样的形式为表达式。 对于 $a(\text{表达式})$ 这样的形式，表示写 $a$ 遍表达式表示的数。 运算优先级是 $(), +, -$ 从高到低。 考虑建立一个表达式树，进行分治处理。 感觉这里最妙的一点就是节点的合并。 因为我们节点的合并可能是重复写很多次，我们不妨记录节点的数值和长度作为一点类。设其为 $(x, y)$。 我们分类讨论一下合并的情况： $a + b$。$(a_x \times 10^{b_y} + b_x, a_y + b_y)$。 $a(b)$。$(b_x \times ({(10^{b_y})}^{a_x} - 1) \div (10^{b_y} - 1), b_y \times a_x)$。这里代码 ...