拉格朗日反演及扩展拉格朗日反演 如果有 \(F(G(x))=x\)，即 \(F,G\) 互为复合逆，同时一定有 \(G(F(x))=x\)，可以称 \(G(x)=F^{-1}(x),F(x)=G^{-1}(x)\)。 在这种情况下，有这样的式子： 拉格朗日反演 \[[x^n]F(x)=\frac{1}{n}[x^{-1}](\frac{1}{G(x)})^n=\frac{1}{n}[x^{n-1}](\frac{x}{G(x)})^n \] 扩展拉格朗日反演 \[[x^n]H(F(x))=\frac{1}{n}[x^{-1}]H'(x)(\frac{1}{G(x)})...

e

##A. 欢迎来到塞莱斯特山 容易想到对每个联通段进行 \(dp\)。 这样在归并子树的过程中只需要枚举两者分别的段数，枚举合并成多少段。 转移系数只要做一个 \(O(n^3)\) 的 \(dp\) 就可以预处理出来。 复杂度大概就是子树归并的复杂度 * \(n\)，写个指针卡卡内存就能过了。   ##B. 感受清风 发现这样的事情，当一个箱子被吹到边界之后就会一直在边界。 对于在边界的箱子，不关注具体是谁，只关注个数。 如果箱子都在边界上，可以直接用线段树维护一下最小值，然后对询问二分找到第一个不合法的位置就好了。 对于存在加入删除操作，可以对线段树可持久化一下，对每一列维护...

##A. 林海的密码 难点主要就是如何构造加法操作。 一个点数 $2 \log n$，边数 $5 \log n$ 的做法是这样的。 像这样构造一个双向的环，显然一个内向生成树为断掉红边的后缀、黑边的前缀。 发现这样每次只能使贡献 \(*2\) 或者不变，所以问题就是用若干个连续的 $2$ 的次幂把 \(c\) 拼凑出来。 容易发现先从小到大倍增，后从大到小倍增就好了。 另一个点数 \(\log n\)，边数 $3 \log n$ 的做法是这样的。 考虑保留了哪条红边，那么红边以下的点均有 $2$ 种选择，红边以上的点选择唯一。 所以可以根据 \(c\) 在二进制下哪些位为 $1$ 选出...

##A. 黑白沙漠 考虑这样一个做法，对于每个点处理出左侧和右侧分别的最优决策点，然后比较二者谁更优即可。 当然这样的点可以表示为若干个区间，对于其中每个区间，左右侧谁更优是单调的，可以通过二分求解。 所以问题就是如何处理出这样的若干个区间。 可以想到这个最优决策点就是上凸包会切到的点。 所以写一个单调栈维护就好了。   ##B. 荒野聚餐 学习了一下如何做线性规划对偶，大概可以这样做： 首先将对偶的式子化为标准型，最小化变量，约束条件为一些变量 \(\geq\) 常量，并且每个变量 \(\geq 0\)。 对每个约束条件设置一个对偶变量，对偶问题就是用这些对偶变量尽量去表示出一个下界，切...

##A. 小B的班级 莫名想到了一个结论，这种题可以找到选中的点形成的重心。 然后求所有点与重心距离的和即可。 原因是，任意一个子树大小均小于 \(m\)，所以总可以构造出方案。 在这道题中，只要枚举最接近 $1$ 号点的可能的重心，然后计算方案数就可以 \(O(n^3)\)。 仔细想一下，可以把每个点到达重心的距离摊到每条边的贡献上。 直接套用上面得出的结论，可以知道贡献的系数就是 \(\min\{sz_a,sz_b\}\)，然后随便写写这题就没了。   ##B. 小B的环 首先断环成链，把所有相邻并且相同的位置打个标记。 每次的操作就是要求覆盖环内所有标记，找出位置不同的两个点，然后做类...

##A. zsy家今天的饭 对于 \(\binom{m}{k}\) 种方案，答案是跨过的边权*2-直径。 可以对两部分分别计算贡献。 对于前者，可以考虑计算每条边的贡献。 若将餐厅点集划分为 \(a,b\) 两部分，那么乘上的系数就是 \(\binom{m}{k}-\binom{a}{k}-\binom{b}{k}\)。 对于后者，可以考虑枚举直径的两个端点是谁。 有个结论是，树上到达每个点最远的点，一定在直径的端点上。 所以对于其它点，只要判断与当前枚举端点距离即可。 有个问题是如何处理直径长度相同，通过讨论可以发现只要比较标号就是正确的。   ##B. 划愤 考虑 \(n=2\) 的...

A. ⼩W数排列 做过类似的题，思路大概将所有数从大到小插入。 这样相邻两个位置的贡献就转化为一加一减。 可是这样做会导致值域变得很大，其实这样没用到题中 \(l\) 很小的限制。 考虑这样一个做法，把每次一加一减的贡献差分掉。 每次基准线降低的时候直接统计 降低的高度*降低的个数 的贡献。 因为这个贡献是不降的，所以维护到 \(l\) 就够了。   B. ⼩W玩游戏 容易发现行列之间是没有关系的，每次的操作就是改变一行一列的奇偶性。 可以首先处理出选 \(i\) 个奇数行的方案数 \(f_i\)，选 \(j\) 个奇数列的方案数 \(g_j\)。 那么它们对答案造成的贡献为 \([i...

A. 钩子 可以发现大概问题是一层一层的。 对于每一层，一定会选完所有长度为 \(2x,2x-1\) 的连续段之后递归下一段。 可以考虑将这样的选择合并在一起考虑，然后做一个 \(dp\)。 可以发现概率的大小大概只与剩下的奇数、偶数段的个数有关，所以记录奇数段的个数就可以转移了。 然后的问题是怎么继续考虑下一层。 比较简单的是奇数段，只要选中间一个点就好了。 对于偶数段，选择两种可能都是可以的。 但是容易发现这样的事情：不同的段之间不会相互影响，相同段的左右两半是对称的。 所以可以钦定这次的选择是偶数段的靠左的中点，在递归结束之后对所有答案按照对称轴取个平均数就好了。   B. 加减 ...