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)$。这里代码 ...

CF1548C The Three Little Pigs 算基础的生成函数题了吧。 反正当时隔壁老哥在打 VP 的时候，推了半天 $C$ 没有推出来。被我一眼秒了 $\dots$ 就是答案肯定是 $\sum_{i = 0} ^ {n} \binom{3i}{x}$。 发现这个东西就是个二项式定理。 那么如果写成生成函数就是 $[z^x] (1 + x) ^ {3i}$ 设 $F(x) = \sum_{i = 0} ^{n} (1 + x) ^ {3i}$ 求通项可以得到。$$F(x) = \frac{(1 + x) ^{3n + 3} - (1 + x) ^ 3}{(1 + x)^3 - 1}$$上面那个二项式定理展开可以 $O(1)$ 计算每一项。 之后下面那个直接暴力除法就好了。 大神可以跳过这一段 下面那个柿子展开是 $x^3 + 3x^2 + 3x$。 我们考虑对于一个最高次是 $y$ 的多项式，我们除法第一遍做的商肯定是 $y - 3$。 那么得到 $x^y + 3x^{y - 1} + 3x^{y - 2}$。之后这个是要减 ...

CF1528F 其实不难，但是又有懂得都懂的感觉。 某谷的翻译真的鬼畜。 题目大意： 一个合法的序列 $A$ 是 $\forall j \le n, \sum_{i = 1} ^ n [a_i \ge j] \le n - j + 1$。 给了一个限制 $B$ 序列，要求 $a_{b_1} = a_{b_2} = \dots = a_{b_k}$ 求这样 $(A, B)$ 的数量和。 首先考虑 $A, B$ 看起来很独立，我们考虑分开计算。 对于 $A$ 的限制我们不妨改变一下。 看成有 $n$ 个人，每个人都选择了一个位置 $a_i$。每个人依次坐其选定的位置，如果这个位置有人了那么就向右坐一个位置。如果 $n + 1$ 这个位置没有人，就是合法的。 我们考虑总方案是 $(n + 1) ^ n$ 然后对于一个合法位置其经过变换可以得到 $n$ 个不合法的位置。 那么合法的方案就是 $(n + 1) ^ {n - 1}$。 然后考虑 $B$ 的计数，因为只要满足 $a_{b_1} = a_{b_2} = \dots ...

CF 1466H 话说某谷的翻译直接讲了第一步 $\dots$ 题目大意： 总共有 $n$ 个人，每个人有一个长度为 $n$ 的排列，其中越靠前的数，其越喜欢。 对于一个序列 $A$，一开始分配的方案是 $i$ 号人分配到 $A_i$。 称一个序列 $A$ 是合法的，当且仅当不存在两个或者多个人交换 $A_i$ 使得有人得到更加喜欢的数。 给定一个数组 $A_i$ 求出有多少个排列，满足 $A$ 是合法的。 排列指的是每个人都喜欢序列。 发现如果一个序列不合法肯定存在一个置换使得有人可以更优。 置换本质就是环，我们考虑建图，对于一个 $j$ 在 $A_j$ 前面的点向其连接黑色的边。当然我们有 $j \to A_j$ 这个是白色边。如果存在一个环其中有黑色边就不合法。 我们只考虑确定的位置就是 $j \to A_j$ 的边。 如果点 $i$ 连接入了 $x$ 条黑边那么方案数就是 $g(x) = x! \times (n - x - 1) !$ 。 这个本质就是一个 $n$ 个点有标号的 $DAG$ 计数问题。 设 $dp(i)$ 就是答案。 我们枚举一下总共有多少个 ...

P6031 CF1278F Cards 加强版题目大意： 有 $m$ 张牌，其中有一张是王牌。将这些牌均匀随机打乱 $n$ 次，设有 $x$ 次第一张为王牌，求 $x^k$ 的期望值。 答案对 $998244353$ 取模。 首先 $x^k$ 不好处理。考虑将其消除掉，会想到使用斯特林数转下降幂之后使用组合数消除掉。 我们考虑枚举几次是王牌。$$Ans = \sum_{i = 0} ^ n \frac{1}{m^i} (\frac{m - 1}{m})^{n - i} \binom{n}{i} i^k$$不妨设 $p = \frac{1}{m}$。 可以得到 $p^n \sum_{i = 0}^n (\frac{1 - p}{p})^{n - i} \binom{n}{i} i^k$。$$\begin{aligned}&p^n \sum_{i = 0}^n (\frac{1 - p}{p})^{n - i } \binom{n}{i} i^k\&p^n \sum_{i = 0}^ n(\frac{1 - p} ...