我们考虑生成一棵生成树的过程，本质上相当于是选择一些生成树拼起来，而两个生成树拼起来的代价就是把拼接点的权值乘上点的个数积。 于是可以考虑一个 $dp$ ，设 $dp[S][u]$ 表示一个点集 $S$ 组成的根为 $u$ 的树可以得到的最小权值。 于是我们考虑枚举一个子集来进行转移，也就是对于一个子集 $T$ ，我们可以枚举一下这个树的根，然后转移： dp[S][u] = \min\{dp[S][u] , dp[T][v] + dp[S \setminus T][u] + (n - siz[ ...

Interesting Drug考虑选择物品的过程，选择物品就会删掉这个东西，所以相当于是一个扩展区间的过程。 第一步选择 $i$ ，也就是说最开始区间是 $(i,i)$ ，每轮可以扩展到 $(i-1,i)$ 和 $(i,i+1)$ 。 把这个看成一个二维平面上行走的过程，那么我们可以把这个过程倒过来，也就是初始在 $(1,n)$ ，走到 $(i,i)$ 能得到的最大权值。 如果第 $i$ 个物品在 $C_i$ 步被选择，相当于是从 $(i+1,i+C_i-1)$ 走到 $(i,i+C_i-1) ...

第二次学了，上次的文章在这里：生成函数与组合计数 先粘一下以防以后忘了： 这次会以 $F(z),x$ 作为形式幂级数，也就是说后文的 $x,x_0,\dots$ 都是形式幂级数。 前置芝士：泰勒展开，在上次的文章中可以看到。 牛顿迭代 F(G(z)) = 0求 $G(z) \bmod z^n$ 设 $x_0 = x\bmod z^n$ ，考虑求 $x \bmod z^{2n}$ 。 我们将 $F(x)$ 在 $x_0$ 处展开，那么有 F(x) = F(x_0) + F'(x-x_0) + ...

根据 LP对偶（我不会的东西）有这么个结论： 最大费用循环流等价于： \min \sum_{(u, v) \in E} c(u, v) \max \left(w(u, v)+h_{u}-h_{v}, 0\right)其中 $h_u$ 是给每个点任意定的一个权值，$c(u,v)$ 为一条边的容量，$w(u,v)$ 为一条边的费用。可以带入最大流和最小割验证。 对于这个题，如果二分答案为 $\lambda$ ，我们相当于是要最小化 \sum x_{u,v}满足 d_u + x_{u,v} + ...

首先，跑两千次 dijk 或者 spfa 肯定是不行的。 发现每次只会给边权加一，并且一共才加 $10^6$ 次，所以最短路长度的增加量其实只有 $10^6$ 级别。 我们考虑去求这个增加量。有一个操作：先设最开始跑一遍最短路后 $1$ 到 $u$ 的最短路为 $dis_u$ ，对于一条边 $u\to v$ 设其权值为 $w$ ，那么把它的权值改成 $w + dis_u - dis_v$ 。由于 $dis_u + w \ge dis_v$ 所以这个值肯定是非负的，且如果这条边在 $1$ 到 $v ...

昨天写了忘发了。。 考虑容斥，设 $f(i)$ 表示钦定了 $i$ 个数只出现了 $\le 1$ 次时的方案数量，那么答案显然等于 ans = \sum_{i=0}^n (-1)^i f(i)考虑我们钦定的 $i$ 个数，显然可以直接假定为 $1\sim i$ ，最后再乘个 $\binom n i$ 的系数即可。 先考虑除开前 $i$ 个的数，这些数是没有限制的，他们可以组成集合的方案数量是 $2^{2^{n-i}}$ 种，因为任何一个这 $n-i$ 个数的子集都可以作为某一种集合出现或者不出 ...

Day 0Day 0 居然放假。。在家里打了下各种多项式板子认真背了下 ppt 上的经典套路。。 据说要考多项式，字符串和计算几何？ 考到计算几何就放弃吧（？）大概写了下凸包和半平面交。。反正几何算是知识盲区了。。不过按照前几年的惯例SC出几何多半全场都不可写吧（确信。。（mmp后来证明毒奶了） 背不到SA，写了下后缀平衡树（写不来SA要排序就上这个反正复杂度一样）SAM 写了一下还是忘不掉的，PAM 前两天也复习过了。 假装准备得很充分了。。晚上和 wkr 和 ywh 颓了会儿 arc 。。 ...

由于是做题时写的思路所以可能很乱 /kk 首先考虑 $k = 1$ 的情况。我们希望对于每一个 $i$ 求出一个 $j$ 使得 $\gcd(i,j) = 1,\max |a_i - b_j|$ 。 考虑把绝对值拆开，对于每个 $i$ 分别求最大的 $b_j$ 和最小的 $b_j$ 。这两个问题明显是对称的，考虑求最大的 $b_j$。 我们可以整体二分一下，比如当前二分的数为 $x$ ，把 $\ge x$ 的数的编号拿出来放到一个集合里面。我们预处理出每个编号的所有质因数 （$O(\log n)$ ...

比赛链接 A 异或树考虑假设我们已经确定了最高位，则可以按照最高位为 0/1 分成两类。 而最小生成树必然是两边连成一个联通块，中间再连一个边。我们可以分别算这两类贡献。 显然，最高位全是 $0$ 和最高位全是 $1$ 砍掉最高位后是一个子问题（只是少了一位），可以递归下去做。 注意 $n$ 很小，我们可以枚举一边联通块的大小（另一边就已经知道了），递归算 $ans(i,m-1)$ 。然后对于左边的所有方案和乘上右边的方案数量，对于右边的所有方案和乘上左边的方案数量，最后再乘一个组合数即可。 现 ...

比赛链接 A qiqi20021026 的 T1这题出的真离谱。。 考虑 $O(qn)$ 怎么做。显然建 trie 树后直接在上面求子树内第一个串的个数和第二个串的个数的最小值贡献在答案里面就行了。 正解，直接上四维莫队。由于 $n$ 比较大，串长期望很小，可以看成移动 $O(1)$ ，然后复杂度 $O(nq^{\frac 3 4})$ （莫队复杂度）。 为什么能跑过去 我也不知道啊。。玄学 。题解写了最后一个指针的移动次数实际上不多。。 $n\le 10^4 , q\le 5\times 10 ...

616模拟赛题目背景是 arcaea B Tempestissimo抽象一下，这题相当于有一个盒子里面有 $n$ 个球，其中 $m$ 个关键球，求期望抽出所有关键球的时间。 我们可以考虑倒过来，也就是求期望抽出第一个球的时间，最后由 $n$ 减去即可。 考虑这个东西本质上就是 \sum_{i=1}^{n-m} P[这个球在第一个关键球之前被抽出]如果我们把关键球先加进去，每个球在哪两个关键球直接抽出本质上是相同的。由 $m$ 个关键球可以分成 $m+1$ 段，于是概率就是 $\frac{1}{ ...

比赛链接 A sequence首先，和谐的数列可以仅由前两个数递推得到。然后可以证明，如果第一个数确定，答案关于第二个数凸，如果第二个数永远取最优，答案关于第一个数凸。所以可以直接三分套三分来做。但是这样是 $O(n\log^2 v)$ 的，很可能会被卡 T 。 考虑和谐的序列的循环节一定是 $6$ ，所以可以对于 $\bmod 6$ 的所有值分别整个 vector 再做个前缀和，查询可以直接从每个 vector 二分。复杂度 $O(n\log n + \log^3 v)$ 当然，也可以暴力整凸 ...

现在看了看以前的题感觉好妙啊。。多校的时候好像是找出原题直接做的。。 为了回答询问，可以贪心地做前缀的线性基。由于只有 append 操作，可以方便地维护这个。 对于 $1\sim i$ 的线性基，我们可以对每个位置记一个编号，表示能够选择这一位的最靠右的数编号是什么。 在插入一个数到线性基的时候，从高到低位考虑，如果这个数比这个位置上的数更靠右且这个数可以更新这一位，我们可以把这个数和线性基中这个数字交换一下，再更新编号，然后继续向低位更新。 考虑正确性，对于一个位置，它显然只会被比它的编号高 ...

我们考虑把输入的矩阵看成邻接矩阵，于是相当于是给了个图。 然后考虑询问，1 的位置就相当于前后有边相连，0 的位置就相当于没有边。于是相当于通过 1 分成了很多个联通块，这些联通块之间不能有边，求可以满足这个条件的排列个数。 这个不好求，我们考虑求钦定了某些位置有边，剩下无限制的方案数量，最后做一次逆与卷积即可。因为设 $F[s]$ 表示钦定了 $s$ 集合的 $1$ 的位置有边，剩下无限制的方案数量，$f[s]$ 表示恰好只有 $s$ 的 $1$ 的位置有边的方案数量。我们显然有 F[S] ...

我们考虑对每行没列 $\min-\max$ 容斥。 考虑某种状态（行列的状态）每个集合内部的元素（一行或者一列）出现了一个数的最大时间，也就是全部都有数的时间（类似 [HAOI2015]按位或）。由于式子 \max(S) = \sum_{T\sube S} (-1)^{|T|+1} \min(T)也就是我们得算的实际上是每种状态（一些行与列）中的数第一次被选到的期望时间。 如果我们实际枚举了行列的状态，对于每个状态，设这些行列的和是 $x$ ，那么贡献就是 $(-1)^T\frac {tot} ...

考虑对于每一个右端点 $r$ ，维护 $ans_i$ 表示 $\min |a_i-a_j|,j\in[i,r]$ 。 那么如果我们离线下来询问，我们要求的 $[l,r]$ 的答案就是一段后缀的最小值。但是为了保证复杂度，事实上我们维护的 $ans_i$ 只是保证了一段后缀的最小值就是 $[l,r]$ 的答案，而 $ans_i$ 是可能大于 $\min |a_i-a_j|,j\in[i,r]$ 。 现在考虑我们把 $r - 1$ 移动到了 $r$ ，并且已经维护好了右端点为 $r - 1$ 时的 ...

考虑跑出 dfs 树。如果两个点在 dfs 树上路径本身长度就是奇数，可以直接走过去。 否则，相当于可以在这两点之间的路径上有两个点 $u,v$ ，可以通过在 $u$ 离开 dfs 树上的路径然后从 $v$ 回来继续走到另一个点的方式改变奇偶性。不难发现，这个条件等价于 $u,v$ 之间的路径存在于一个奇环上。同时我们还有一个结论，一个点双（因为这题要求点不相交）内部如果有一个奇环，那么点双内部任何两个点都处在一个奇环。 于是我们考虑给所有点双内有奇环的点打个标记，然后树上差分，询问的时候就询问 ...

考虑一次查询，比如查询 $[l,r]$ 区间。 首先找出区间内最小值的位置，设为 $pos$。 考虑把询问的区间的子区间分成三种： 跨过了 $pos$ 左右端点都在 $[l,pos-1]$ 左右端点都在 $[pos+1,r]$ 考虑分别处理。对于第一种，明显贡献是 $(pos-l+1)(r-pos+1)$ 。 下面设 $[l,r][L,R]$ 表示左端点在 $[l,r]$ 内，右端点在 $[L,R]$ 内的所有区间的最小值的和。 我们考虑怎么求 $[l,r][l,r]$ 的值。我们把这个拆成 ...

一种用来求最短线性递推的奇妙算法。复杂度是 $O(n^2)$ 。 忘了怎么做建议看看这个博客，很清楚了。 模板题 CF848E 123456789101112131415161718192021222324252627int Pow( int x , int a ) { int ans = 1 , cur = x % P; while( a ) { if( a & 1 ) ans = 1ll * ans * cur % P; c ...

原题：CF914H 答案乘 $2n(n+1)$ 即可。 我们考虑题目要求的限制相当于是每一条路径必须是单峰或者单调的。 于是对于一个合法的树我们一定可以找到一个点，使得这个点到所有点的路径一定是单调的。考虑如果不存在这个点，那么对于一个单调的路径的一个峰的位置，它不能作为这个点，所以它向下有个路径的编号是单峰的。画下图，无非这两种 明显这两种都不满足题意。。 考虑对于当前的根，如果它只有一个儿子是递增的，其他都是递减的，那么明显可以把根往这个方向移，这个根仍然合法。如果有两个儿子都是递增的， ...

A 第一题考虑建出子序列自动机。现在有了一个 DAG。 有两种做法。 我们可以按照子树内 dp 值最大（含的子序列个数最多的）儿子作为重儿子。类似地做轻重链剖分。考虑如果走了一条轻边，往轻儿子走明显答案至少会减半。 否则，我们会往重儿子走很多次。可以倍增来走重儿子。 麻烦点在于输出。有一种很优秀的实现方式，考虑先按照这样的方式跳总长度 - p 次，然后暴力跳 p 次即可。 要对 $10^{18}$ 取 $\min$ ，否则路径总数是指数级别的，直接做会爆炸。 还有一种 zjk 的神仙做法。考虑连 ...

首先考虑暴力，显然，这个东西答案就是每条边的贡献的和，每条边的贡献就是这条边两边分别选的有点的方案数量。写出来就是 tot^k - siz^k - (tot - siz)^k注意到这个题的性质：每个点的子树内点的值都是 $u$ 到某个值的一段区间。容易发现画出来后需要考虑的叶子总是这样的一些子树（图中橙色的子树）。 我们考虑除开 $L$ 和 $R$ 的橙色子树。这些子树内的点的子树都必然会选完所有叶子。如何快速的查这些点向上的边的贡献？明显 $siz^k,tot^k$ 很容易计算，考虑怎么算 ...

怎么都没人写好写又好懂的官方题解的做法？ 考虑对询问分块。 设块大小为 $s$ ，那么每一个询问块用到过的点的数量是 $O(s)$ 的。 考虑把询问的这 $s$ 个点拿出来建虚树（这里可以 $O(n)$ 建虚树的）。我们对于一个虚树上的边，存一下这边在原树上的点的个数，白色点的个数。 然后考虑第一个操作，我们可以直接在新树上模拟进行操作。具体来说，修改一个点，如果这个点是白色直接修改，否则查一下当前操作这个点的数量是否足以递归进一个子树。递归操作即可。说白了，对关键点修改直接改，对非关键点延到块 ...

B 漏网之鱼考虑求 $mex$ 这个操作，如果固定左端点，右端点不断向右移动时可以非常方便地维护这个操作。所以我们可以先固定左端点 $1$ ，向右求出每个 $[1,r]$ 的 $mex$ 值。 考虑对所有右端点维护左端点固定的时候的 $mex$ 值，现在考虑如果向右移动一次左端点，如果左端点从 $l$ 变成了 $l+1$ ，假设下一个 $a_l$ 的出现位置是 $p$ ，那么不难发现所有右端点在 $p$ 后面的区间都不会受到影响，而所有右端点在 $[l+1,r]$ 的答案会与 $a_l$ 取最小 ...

考虑对行建线段树。对于线段树的每个节点，设节点代表区间为 $[l,r]$ ，对于所有的 $m$ 列在这个区间维护贴紧左、右端点的连续段长度。同时维护对于每列，在这个区间能得到的最大的右端点在这一列的正方形大小。 由于我们维护了这个东西，合并的时候大概就有这样一个图： 首先，连续段长度是非常好合并的。 合并时，只需要考虑跨过了 $mid$ 的正方形。考虑怎么维护每列作为正方形的右边在区间能得到的正方形大小。考虑从左往右枚举右端点 $i$ 。如果左右端点固定，那么竖直的边长就是在区间的上下区间分别 ...

这题可以点分治，但是这里写一个线段树维护凸包的做法。 首先朴素 $dp$ 的式子： dp[u] = \min \{dp[v] - d_vp_u\} + q_u + d_up_u其中 $d_i$ 表示 $i$ 的深度（带权值的），$v$ 是 $u$ 的一个祖先。 考虑由于 $s_i > 0$ ，所以 $-d_v$ 会随着深度变深单调递减，但是 $p_u$ 的变化没有规律。 这种情况往往只需要把最简单的斜率优化的凸包从直接 ++top 变成二分即可。可是这题还有着 $l_u$ 的限制，也就是 ...

首先，所有不同的操作方式是很好求的。但是不同操作序列并不正好对应一种不同的网格。 考虑什么情况下两个操作序列不同但是求出了不同的网格。如果出现了这种情况： 12340 0 1 00 0 1 01 1 1 00 0 0 0 那么明显，要么第三行 +3 ，第三列 +2 或者 第三行 +2 第三列 +3 ，会出现两种不同的状况。 除开这种情况，不会有出现两种不同操作序列对应同一个网格图了。神仙zjk已经教了我一个绝妙的证明，可惜我懒得写下来了（逃 我们将一个导致操作序列出现不同的位置称为一个拐角，那么 ...

考虑用后缀平衡树来维护这个东西。 后缀平衡树是一种维护后缀的数据结构，其中序遍历就是后缀数组。但是，对于它维护的后缀集合 $T$ 其中的一个字符串 $S\in T$ ，它可以支持 $O(\log n)$ 插入 $xS$ 。 我们考虑插入 $xS$ 的时候要做什么，首先会比较当前节点所代表的后缀的第一个字符和 $x$ 的大小关系，如果不相同，我们就已经成功比较了当前节点的后缀和这个串的大小关系。否则，我们需要比较 $S$ 与这个后缀去掉第一个字符（仍然是个后缀）的大小关系，也就是某两个后缀的大小关 ...

模拟赛的 A 题。 $dp[i][j][0/1][0/1]$ 表示当前在第 $i$ 轮，进行到了第 $j$ 场（我们把失败组的比赛和失败组胜利者与胜利组失败者的比赛压缩到一场），这一场打完了你是否是胜利者的粉丝，是否是失败者的粉丝。 然后发现这是一个类似线段树的结构，如果从 $0$ 编号，第 $i$ 轮的第 $j$ 场会由 $i-1$ 轮的 $2j,2j+1$ 转移过来。 如果是一个队的粉丝，那么显然我们会贪心地让这个队伍存活下去，不会出现一个非粉丝的队伍在失败组淘汰掉一个粉丝的队伍。因此我们不 ...

考虑如果不强制在线，我们可以建 SAM ，于是 SAM 一个点出现次数就是前缀树子树和。 如果强制在线，也就是我们得动态维护前缀树，一个简单想法就是拿 LCT 来维护前缀树。 于是我们需要写一个 LCT ，但是显然是不需要支持 makeroot 的。 同时我们还需要求子树和。可以在 LCT 上维护子树和，具体做法就是插入一个点后直接给这个点到根的链全部 +c 。这个东西是不需要 pushup 的，删除一个点就是一个点 access 后左子树内的点全部 -c（也就是它到根的路径 -c）即可。维护这 ...