2021-03-01~2021-03-31¶

CF1483D¶

题意¶

给定一个 $n$ 个点 $m$ 条边的简单无向图，$q$ 个三元组 $(u,v,l)$，问有多少条边 $e$ 满足下列条件：

存在一个三元组 $(u,v,l)$，以及一条从 $u$ 到 $v$ 的长度不超过 $l$ 的路径，且该路径经过 $e$。

($2 \le n \le 600$，$0\leq m\leq \dfrac{n(n-1)}2$，$1\leq q\leq \dfrac{n(n-1)}2$)

题解¶

先跑 floyd 求出任意两点间最短路 $d_{i,j}$。

再对每个点对 $(i,j)$ 求出 $f_{i,j}$，表示对于所有三元组，当 $j=u$ 时，$l-d_{i,v}$ 的最大值。

再枚举每条边 $(i,j)$，枚举三元组的一个端点 $u$，如果 $d_{i,u}+1 \le f_{j,u}$ 或 $d_{j,u}+1 \le f_{i,u}$ 则该边满足条件。

总时间复杂度 $O(n^3)$。

CF1491G¶

题意¶

有 $n$ 个硬币，第 $i$ 个位置上的硬币为 $c_i$，保证 $c_1,c_2,\cdots,c_n$ 是一个 $1$ 到 $n$ 的排列。初始，所有硬币均朝上，你可以进行至多 $n+1$ 次下述操作：

将第 $i$ 个位置和第 $j$ 个位置的硬币互换，并将它们翻面。

最终需要使得第 $i$ 个位置上的硬币为 $i$，且所有硬币均朝上，构造一种方案，不必最小化操作数。($3 \le n \le 2 \times 10^5$)

题解¶

考虑建图，第 $i$ 个位置向 $c_i$ 连一条有向边，每个位置对应的点有两种颜色，红色代表该位置的点为正面，蓝色代表该位置的点为反面。最终我们想达到的目标即所有点均为自环且为红色。

对于一次操作，相当于将 $i,j$ 指向的点互换，同时将两者颜色互换后翻转。

对于两个环，我们在一个环上各选一个点进行操作，可以得到一个大环，且环上有两个蓝点，不断选择操作一个蓝点 $i$ 和该蓝点指向的点 $j$，结果为 $j$ 成为红色的自环，$i$ 仍是蓝点且指向 $j$ 所指向的点。最终剩下两个蓝点进行一次操作即可变为两个自环的红点。设这两个环大小之和为 $m$，则我们一共操作了恰好 $m$ 次。

但是，如果环的数量是奇数，就不好配对了，分两种情况讨论：

如果所有环的数量 $x$ 不为 $1$，那么我们可以先将 $x-1$ 个环按上述方法配对，再令最后一个环和一个单独的自环红点配对即可，这样只需多做一次操作。
如果恰好只有一个环，可以通过两次操作将整个环变为恰有两个蓝点的环：设按环的顺序初始三个点为 $i,j,k$，操作 $i,j$ 再操作 $j,k$，则环顺序改为 $i,k,j, \cdots$，且 $i,j$ 是蓝点，之后按上述方法来进行 $n-1$ 次即可。

综上，如果环的数量是奇数，只需 $n+1$ 次，否则只需 $n$ 次。

CF1491H¶

题意¶

给出一颗 $n$ 个节点的树，$1$ 号点为根节点，第 $i$ ($i > 1$) 个节点的父亲为 $a_i$，保证 $a_i < i$，有 $q$ 次如下两种操作之一：

给定 $l,r,x$，对所有 $l \le i \le r$，将 $a_i$ 变为 $\max(a_i-x,1)$。
给定 $x,y$，询问 $\operatorname{lca}(x,y)$。

($2\leq n,q \leq 10^5$)

题解¶

考虑将所有节点按下标分成连续的 $\sqrt n$ 块，对于每个节点维护 $f_i$，表示所在块内深度最小的祖先，如果不存在这样的节点，则 $f_i=i$。

考虑我们这棵树的特点，有 $a_i < i$ 恒成立，从而必然不存在 $x,y,z$ 使得 $y$ 是 $x$ 的祖先，$z$ 是 $y$ 的祖先，但 $x,z$ 属于同一块，$y$ 和 $x,z$ 不属于同一块。（形象地说就是不存在一条从下到上块内点出现不连续的链）

因此对于 $f_i$ 的求解，只需从小到大枚举 $i$ 扫一遍即可，即如果 $a_i$ 和 $i$ 是同一块的，则 $f_i=f_{a_i}$，否则 $f_i=i$。

我们考虑对 $a_i$ 进行区间减时如何快速维护 $f_i$：

对于两端的部分，直接暴力修改 $a_i$ 并更新该块即可，时间复杂度不超过 $O(q\sqrt n)$。
对于中间的数个整块，先对 $a_i$ 进行区间的标记，再考虑暴力修改 $f_i$，注意暴力修改 $f_i$ 的操作每个块至多进行 $\sqrt n$ 次，因为每次至少减少 $1$，当操作次数超过 $\sqrt n$ 时该块内所有 $a_i$ 必然有 $i-a_i > \sqrt n$，从而必然有 $f_i=i$，即 $f_i$ 不会发生改变，因此记录一下修改次数，超过后就不再对 $f_i$ 进行暴力修改。那么这一部分均摊下来总复杂度不超过 $O(n\sqrt n)$。

利用 $f_i$ ，我们可以在 $O(\sqrt n)$ 的时间内求出两个节点 $x,y$ 的 $\operatorname{lca}(x,y)$：

如果 $f_x=f_y$，则进行下一步；否则不妨设 $x>y$，令 $x=a_{f_x}$。
如果 $x=y$，则该点即为所求答案；否则不妨设 $x>y$，令 $x=a_{x}$。

上述过程类似倍增求 $\operatorname{lca}$，利用上述所说 $a_i < i$ 所带来的条件，如果 $f_x\ne f_y$，那么 $\operatorname{lca}$ 必然还在上面，因此直接向上跳；如果 $f_x= f_y$，那么 $\operatorname{lca}$ 必然在当前块，同样暴力跳即可。

综上，总时间复杂度即为 $O\big((n+q)\sqrt n \big)$。

CF1493E¶

题意¶

给定 $n,l,r$，求下式的值： $$ \max_{l \le x \le y \le r} \bigoplus _{i=x}^yi $$ ($1 \le n \le 10^6$，$0 \le l \le r < 2^n$)

题解¶

分情况讨论：

当 $l$ 和 $r$ 最高位不同，则答案为 $2^n-1$，取 $x=0111\cdots1111$，$y=1000\cdots0000$ 即可。
否则，当 $r$ 为奇数时，答案为 $r$，使用数学归纳法进行证明：
右端点 $r$ 为奇数， $r=l$ 或 $r=l+1$ 时答案显然为 $r$。

假设右端点 $r$ 为奇数，区间为 $[l,r]$ 时答案为 $r$，那么对于区间 $[l,r+2]$：
- 所选区间 $r+1 \le x \le y \le r+2$，最大值显然为 $r+2$。
- 所选区间 $l \le x \le y \le r$，由归纳假设，最大值为 $r$。
- 所选区间 $l \le x \le r$，$y=r+2$，相当于两个区间 $[x,r]$ 和 $[r+1,r+2]$，前者由归纳假设最大值为 $r$，后者因为 $r+2$ 是奇数从而异或值恒为 $1$，而 $r$ 是奇数，因此最大值不超过 $(r-1) \oplus 1 =r$。
- 所选区间 $l \le x \le r$，$y=r+1$，假设最大值 $x$ 超过 $r+2$，那么 $x$ 和 $r+2$ 相比必然存在一个非最低位由 $0$ 变为了 $1$，由 $r+2$ 最低位为 $1$ 易得从 $r+1$ 往小到该位第一次出现 $1$ 一共有奇数个数，设上面这部分为第一部分，接下来的部分为第二部分。而后面该位为 $1$ 和该位为 $0$ 的数都是连续出现，且出现次数均为偶数（因为不是最低位），从而如果这一位要选奇数个 $1$，必然要选择奇数个数。从而两部分均为奇数，加起来选择了偶数个数，从而异或起来最高位必然为 $0$，最大值必然小于$r+2$，因此矛盾，所以假设不成立，最大值不超过 $r+2$。（下面为官方题解的图片）
否则，当 $r$ 为偶数时，如果 $l+2 > r$，显然答案为 $r$。否则选择区间 $x=r-2$，$y=r$ 时答案即为 $r+1$，容易证明此时答案达到上界：显然区间为 $[l,r]$ 的最大值不会大于 $[l,r+1]$ 的最大值，因此我们可以考虑区间为 $[l,r+1]$ 的最大值，$r+1$ 为奇数，由上述论证答案即为 $r+1$。

CF1493F¶

题意¶

交互题，给定 $n$ 和 $m$，有一个未知的 $n \times m$ 矩阵 $A$，你需要求出有多少个数对 $(r,c)$ 满足将 $A$ 分为 $\dfrac{nm}{rc}$ 个互不重叠完全相同的 $r \times c$ 的子矩阵。你可以做至多 $3 \left \lfloor{ \log_2{(n+m)} } \right \rfloor$ 次如下询问：

询问以 $(i_1,j_1)$ 和 $(i_2,j_2)$ 为左上角的大小为 $h \times w$ 的子矩阵是否完全相同，要求这两个子矩阵不能重叠。

($1 \le n, m \le 1000$)

题解¶

首先行和列的相互独立的，即 $(r,c)$ 合法 $\Leftrightarrow$ $(r,m)$ 和 $(n,c)$ 都合法，左推右显然，右推左考虑证明任意两个对应大小的子矩阵都相同，分别利用两个条件先跳到同一行再跳到同一列即可，这里的行和列是指分割后的行与列。

题目转化为求出行的最小循环节和列的最小循环节，类似字符串求最小循环节，质因子分解后拿每个质因子去试除即可。但是字符串判断循环节时，设需要判断的循环节长度为 $x$，使用的是判断 $[1,n-x]$ 和 $[x+1,n]$ 两者是否相同，但本题中子矩阵不允许重叠，因此我们需要稍微修改一下判断方法：（设 $p$ 是要试除分割的段数）

当 $p=2$ 时，直接判断两个部分是否相等即可，显然它们不重叠。
当 $p > 2$，长度为 $n$ 的子矩阵被分为了 $p$ 段。因为 $p$ 是质数，从而必然是奇数。以段数为单位，如果这三个区间 $\left[1,\dfrac{p-1}{2} \right],\left[\dfrac{p-1}{2}+1,p-1\right],\left[\dfrac{p-1}{2}+2,p\right]$ 相等，那么分割就是合法的：

即从第 $\dfrac{p-1}{2}+1$ 段开始满足 $\dfrac{n}{p}$ 是一个循环节，而前面的部分 $\left[1,\dfrac{p-1}{2} \right]$ 又和 $\left[\dfrac{p-1}{2}+1,p-1\right]$ 相等，后者满足 $\dfrac{n}{p}$ 是一个循环节，且两者循环节相同，从而整体满足 $\dfrac{n}{p}$ 是一个循环节。

因此分别询问第一个和第二个区间是否相等，第一个和第三个区间是否相等即可，如果这两个询问均成立，则等价于上述三个区间均相等，且询问两两不重叠。

询问次数最多的情况显然是 $p=3$，每次 $n$ 缩小 $3$ 倍，需要询问 $2$ 次，至多需要 $2\left \lfloor{ \log_3{n} } \right \rfloor$ 次，从而总次数不超过： $$ \begin{aligned} &2\left \lfloor{ \log_3{n} } \right \rfloor + 2\left \lfloor{ \log_3{m} } \right \rfloor \newline \le& 4\left \lfloor{ \log_3{(n+m)} } \right \rfloor \newline =&\frac{4\log_2{(n+m)}}{\log_2 3} \newline \approx& 2.52\left \lfloor{ \log_2{(n+m)} } \right \rfloor \end{aligned} $$

CF1494F¶

题意¶

给定一张 $n$ 个点 $m$ 条边的无向联通图，你可以从任意点出发，删掉经过的每一条边。你可以在任意时刻开启一个 mode shift 模式，使得开启这个模式后经过的第一条边不删，第二条边删，第三条边不删，第四条边删 ......

开启模式后不能关闭，你可以选择不开启模式，给出一种方案使得所有边都被删完，或判断无解。($2 \le n \le 3000$，$n - 1 \le m \le \min(\dfrac{n(n-1)}{2}, 3000)$)

题解¶

如果开启 mode shift 后将图走完的话，开启 mode shift 后所删掉的图必然是一个菊花图，证明如下：

考虑删掉的最后一条边 $(u,v)$，不妨设最后一步为从 $u$ 走到 $v$，那么倒数第二步不能删边，而图上和 $v$ 相连的只有 $(u,v)$ 这一条边，因此必然是从 $v$ 走到 $u$。

重复上述过程，易得到开启 mode shift 后一直在 $u$ 和其相邻的点间一来一回，从而所删掉的图必然是一个菊花图。

因此我们只需将原图分为两部分 $G_1$ 和 $G_2$，前者存在以点 $x$ 为结尾的欧拉路径，后者是以点 $x$ 为中心的菊花图。

枚举点 $x$，想让 $G_1$ 存在欧拉路径，必然其中度数为奇数的点只能有 $0$ 或 $2$ 个，因此对于所有一个端点是 $x$ 的边，如果让其加入 $G_2$ 可以让另一端点的度数为偶，就选择加入 $G_2$，否则不选择。之后 check 一次是否满足上述条件。

如果不满足上述条件，可以证明合法情况最多翻转一条边，否则会增加两个奇数的点，分情况讨论：

当 $x$ 度数为奇时，翻转后有至少 $3$ 个度数为奇的点，显然不合法。
当 $x$ 度数为偶时，翻转后有至少 $2$ 个度数为奇的点，即使有 $2$ 个，因为 $x$ 度数为偶，不能作为欧拉路径的起点，因此不合法。

从而枚举每条边是否翻转并进行验证即可，总复杂度为 $O\big(m(n+m)\big)$。

CF1495D¶

题意¶

给定一个 $n$ 个点 $m$ 条边的无向连通图，边权为 $1$。定义一个生成树是点 $i$ 的 BFS 生成树，当且仅当该点在原图和生成树上到每个点的最短距离都是相同的。

对于每个点对 $(i,j)$ ($1 \le i,j \le n$)，有多少个生成树既是 $i$ 的 BFS 生成树又是 $j$ 的 BFS 生成树。

($1 \le n \le 400$，$0 \le m \le 600$)

题解¶

设 $d_{i,j}$ 是 $i,j$ 间最短距离。

考虑对于一个点 $x$ 来说，有多少个生成树是它的 BFS 生成树。bfs 后，将所有满足 $d_{x,j} = d_{x,i}+1$ 的点对连 $i \to j$ 的有向边。可以发现，除 $x$ 点外，每个点的入度都必须为 $1$，因此答案即为这些点入度之积。

考虑对于两个点来说，另一个点设为 $y$，相当于选择的边要符合两个起点不同的上述有向图，直接考虑并不好分析（当时就这里卡死在这里了），仔细想想可以发现，单独将 $x$ 和 $y$ 看作起点的话，除了起点外每个点的入度都必须为 $1$，因此如果 $x$ 到 $y$ 的最短路不唯一，那么一定不能满足上述这个条件，此时答案为 $0$。

感性证明：假设从 $y$ 出发，最短路到 $z$ 时出现了第一个分叉 $a$ 和 $b$，那么当 $y$ 为起点时显然 $(zz,a)$ 和 $(z,b)$ 都要选，但是当 $x$ 为起点时显然两者只能选一个，否则 $z$ 的入度为 $2$，从而矛盾。

如果 $x$ 到 $y$ 的最短路唯一，那么显然最短路上所有的边都要被选，剩下的边必须满足必须满足 $d_{x,j}=d_{x,i}+1$ 且 $d_{y,j}=d_{y,i}+1$，同样可以类似一个点的情况连 $i \to j$ 的有向边，答案即为除了 $x$ 到 $y$ 最短路上点其它点的入度之积。

$O(n^2)$ 枚举点对后 $O(n)$ 统计，总时间复杂度为 $O(n^3)$。其中确定最短路是否唯一可以计算满足 $d_{i,x}+d_{i,y}=d_{x,y}$ 的节点 $i$ 个数是否恰为 $d_{x,y}+2$。

CF1495E¶

题意¶

$n$ 个人排成一个环，每人属于 A 组或 B 组，每人手里有非零数量的牌 $a_i$，从第一个人开始，出一张牌，然后令他右边第一个和他不同组的且还有牌的人接着出一张牌。重复上述操作，直到其中一组所有人手牌都空了，问每个人出了多少张牌。($1 \le n \le 5 \times 10^6$)

题解¶

首先特判掉所有人都在一组的情况。

先设第一个人所在组的牌的总数不超过另一组，那么这一组的所有人最后都会把牌出光，因为是两组轮流出牌，所以每张牌都会对应另一组的一张牌，考虑这些牌都是另一组哪些人出的。初始令 $x=0$，从第一个人开始，遇到所有的和第一个人同组的人都把所有牌累加到 $x$，遇到另一组的人就让他出 $\min(a_i,x)$ 张牌，并让 $a_i$ 和 $x$ 都减少相同的值，这样绕两圈即可确定每个人出了多少张牌。

感性证明：因为第一组出牌后是找到右侧第一个另一组的有牌的人出牌，所以第一组的人打出牌后，一定是优先让右侧紧接着他的另一组人先把牌出光了，后面的人才可能接着出。绕两圈是因为这是个环，开头可能会被结尾的人所影响。

如果第一个人所在组的牌的总数超过另一组，先让他出一张牌，找到右侧第一个另一组的人，就转化为了上述情况。总时间复杂度为 $O(n)$。

这题越想越 wls。

CF1498F¶

题意¶

$n$ 个节点的树，每个节点都有一定数量的物品。选中一个节点为根，两人轮流操作，每次操作可以将一个点上任意个物品移动到它的 $k$ 级祖先上（如果有 $k$ 级祖先的话），不能操作的人为输，对于每个点为根的情况，问先手是否必胜。($1 \le n \le 10^5$，$1 \le k \le 20$)

题解¶

阶梯博弈升级版，设一个点的深度为 $d$，它是一个有用的点当且仅当 $\lfloor\dfrac{d}{k}\rfloor$ 是奇数。如果是偶数，两人轮流交替操作最后会把对应数量的物品送到不能动的位置，相当于没用了。正常的阶梯博弈是 $k=1$ 的特例。

换根 dp，设 $f_{x,i,j}$ 为以 $x$ 为根的子树中 $\lfloor\dfrac{d}{k}\rfloor \bmod 2 = i$ 且 $d \bmod k = j$ 对应节点数的异或和，时间复杂度为 $O(nk)$。

CF1499G¶

题意¶

给定一个二分图，$n$ 个点 $m$ 条边，你需要给每条边染红色或蓝色，最小化 $\sum \limits_{v \in V} |r(v) - b(v)|$，即所有点邻接的异色边数量之差绝对值的和。有 $q$ 次询问，每次会加一条边，你需要在每次询问后输出染色方案，强制在线。

这题采取的强制在线方案比较新颖，大多数询问只需输出染色方案的哈希值，只有不超过 $10$ 次需要输出完整的方案，且这 $10$ 次输出的方案必须和前一次输出的哈希值完全相同。每次输出后才能读取下一次的输入，类似交互题，需要用到熟悉的 fflush(stdout)。

($1 \le n, m, q \le 2 \times 10^5$)

题解¶

基于二分图的性质，答案始终可以达到下界，即度数为偶的点必然可以 $|r(v) - b(v)|=0$，度数为奇的点必然可以 $|r(v) - b(v)|=1$，考虑如何进行构造：

将所有边划分为数个环和数条链，均为红蓝交替，且每个点至多属于一条链，这样就可以满足上述的条件。

默认每条链从红色开始，维护每条链的左端点与右端点，考虑一条条加边，将新加的一条边视为一条链，那么只需不断将有公共断电的两条链合并即可。合并过程中可能会遇到将一个链颜色全部反转的情况，这可以使用 deque 来实现，需要分四种情况讨论下合并后的顺序（公共端点属于两条链的左/右端点），同时要使用启发式合并，这样总时间复杂度为 $O\big((m+q) \log n\big)$。

另外，如果两条链首尾相接，合并后变成一个环，此时直接删除这两个链即可，因为成环后必然不会再去进行更改了。

CF1500C¶

题意¶

给定两个 $n \times m$ 的矩阵 $A$ 和 $B$，每次可以对 $A$ 选择一列，对这一列进行稳定排序，只不过交换的是整行。构造一种不超过 $5000$ 次操作的方案将 $A$ 变为 $B$，或判断无解。($1 \le n, m \le 1500$)

题解¶

首先，每一行重排后一定得能对应上，这个把每一行放进一个 vector 排序后比较即可，否则一定无解。

整个过程比较类似基数排序，假设我们进行了 $k$ 次操作，那么相当于一次 $k+1$ 关键字对行的基数排序，第 $1$ 关键字为第 $k$ 次操作对应列的大小关系，如果有一些行在该列相同，那么就要去比第 $2$ 关键字，即第 $k-1$ 次操作对应列的大小关系 ...... 最后，第 $k+1$ 个关键字即为 $A$ 中每一列的相对顺序，此时不存在两行大小相同，因此基数排序的结果是可以唯一确定的。

考虑枚举最后操作的那一列，然后再去看能操作哪一列，这样会导致复杂度过高。事实上这是不必要的，仔细结合上述基数排序的流程，可以发现如下算法：

考虑倒序选取操作的列，模拟上述基数排序过程。设 $f_i$ 表示第 $i$ 行是否通过目前选择的列还没有严格大于第 $i-1$ 行，其中 $2 \le i \le n$，初始什么也没选，显然有 $f_i=1$。

我们需要不断选取一列，保证所有 $f_i=1$ 的位置在 $B$ 的该列中有 $b_{i,j} \ge b_{i-1,j}$，否则最终这两列的顺序必然和 $B$ 中不同。同时，选取一列后，可以令所有 $b_{i,j} > b_{i-1,j}$ 的 $i$ 对应的 $f_i=0$，当然已经为 $0$ 的依然保持下去。最终对于所有剩余 $f_i=1$ 的位置 $i$ ，只要 ($B$ 中第 $i$ 行在 $A$ 中位置) 比 ($B$ 中第 $i-1$ 行在 $A$ 中位置) 靠后即合法。

可以看出，每列最多被选取一次，因为选取它后它就将它能改变的 $f_i$ 变为了 $0$，再选取它没有任何意义。

处理出 $b_{i,j} < b_{i-1,j}$ 和 $b_{i,j} \le b_{i-1,j}$ 并放入 bitset，同时也使用一个 bitset 存储 $f$，那么我们只需进行 $O(m)$ 次下列操作：

遍历每一列，利用 $f$ 和每一列 $b_{i,j} < b_{i-1,j}$ 进行与操作，如果没有交则合法，再将 $f$ 和 $b_{i,j} \le b_{i-1,j}$ 进行与操作得到新的 $f$。（当然，后者直接更改不用 bitset 也行，毕竟每次只需 $O(n)$）

如果没有找到合法的列，直接跳出。

总时间复杂度即为 $O(\dfrac{nm^2}{w})$。

本题读入卡常，记得快读。

ABC195F¶

题意¶

给定一个集合 $\{A,A+1,\cdots,B\}$，求有多少个子集使得任意两个元素都互质。($1 \leq A \leq B \leq 10^{18}$，$B-A \leq 72$)

题解¶

利用 $\gcd(x,y)=\gcd(x,x-y)$ 可以得到子集中任意两个元素的 $\gcd$ 不超过 $72$。

预处理 $72$ 以内的质因子，有 $20$ 个，直接状压 dp 即可。设 $f_S$ 为当前的数已经包括了 $S$ 中的质因子的方案数，$S$ 是二进制状态，一个个添加即可。时间复杂度为 $O\big((B-A)2^{\pi(B-A)}\big)$，其中 $\pi(B-A)=20$。

ARC112E¶

题意¶

现在有一个排列 $1,2,\cdots,n$，每次操作可以把一个数放到最前或放到最后，一共进行 $m$ 次操作，问有多少种操作方案使得最终排列为 $a_1,a_2,\cdots,a_n$。($2 \le n \le 3000$，$1 \le m \le 3000$)

题解¶

考虑一个操作为关键操作当且仅当之后没有对这个数进行过任何操作，那么假设进行了 $l$ 次向前放的关键操作，$r$ 次向后放的关键操作，必然有 $a_{l+1},a_{l+2},\cdots,a_{n-r}$ 单增。

对于给定的 $a_1,a_2,\cdots,a_n$，显然第 $i$ 次向前放或向后放的关键操作所操作的数都是确定的。那么当上述 $l,r$ 确定时，如果下面两个量可以确定，对应的操作序列就可以唯一确定：

哪些操作是向前放/向后放的关键操作。
对于其它操作，它所操作的数是后面的哪一个关键操作所操作的数，以及这个操作是先前放还是向后放。

从而可以设 $f_{i,j,k}$ 为考虑后 $i$ 个操作，已经进行了 $j$ 个向前放、$k$ 个向后放的关键操作的方案数，转移为： $$ \begin{aligned} f_{i,j,k} &\to f_{i+1,j+1,k} \newline f_{i,j,k} &\to f_{i+1,j,k+1} \newline 2(j+k)f_{i,j,k} &\to f_{i+1,j,k} \end{aligned} $$ 注意到后两维其实可以合并，设 $f_{i,j}$ 为考虑后 $i$ 个操作，已经进行了 $j$ 个关键操作的方案数，最后再乘以一个组合数 $\dbinom{l+r}{l}$ 即可，转移为： $$ \begin{aligned} f_{i,j} &\to f_{i+1,j+1} \newline 2jf_{i,j} &\to f_{i+1,j} \end{aligned} $$ 最后枚举所有单增的 $a_{l+1},a_{l+2},\cdots,a_{n-r}$，累加答案 $\dbinom{l+r}{l}f_{m,l+r}$ 即可，总时间复杂度为 $O(nm+n^2)$。

ARC114E¶

题意¶

$n \times m$ 的方格图，每次可以找一条非边界的线切断。有两个格子被涂黑，每次等概率地切一条线，如果两个黑色格子留在同一部分上，则保留这一部分扔掉另一部分，并对留下来的这一部分重复上述操作；否则终止操作。求期望切多少次。($1 \le n, m \le 10^5$)

题解¶

显然两个方格所构成的一个矩形内的线都不能切，其它线随便切。

一种 naive 的想法是将线分为两种，然后题目转化为黑球白球随意排列，求第一个黑球出现位置的期望。

这种想法的错误在于切了一刀后扔掉的那部分上面还有一些线，这些线就不能被切到了，而这个模型的转化显然没有考虑这一点。

考虑期望的线性性，矩形内的线最终必然只会被切一刀，最后可以把这个 $1$ 再加上。考虑其它四个方向的线，一条线能被切到当且仅当切它之前没有切矩形内的线，也没有切同方向比它靠内的线。设有 $x$ 个矩形内的线，其它四个方向各有 $a,b,c,d$ 条线，则答案即为：

\[ 1+\sum _{i=1}^a \frac{1}{x+i-1}+\sum _{i=1}^b \frac{1}{x+i-1}+\sum _{i=1}^c \frac{1}{x+i-1}+\sum _{i=1}^d \frac{1}{x+i-1} \]

另一种形象的转化即为，黑色球和四种其它颜色的球，其它四种颜色的球内部每个球有一个编号。对于这些球，随机排列下，它前面没有黑色球也没有比他编号小的同色球的概率。

时间复杂度为 $O(n+m)$。

ARC115D¶

题意¶

$n$ 个点 $m$ 条边的简单无向图，每条边可删可不删，求恰有 $k=0,1,\cdots,n$ 个点度数为奇的方案数。($1 \le n \le 5000$，$0 \le m \le 5000$)

题解¶

天秀结论题。

先考虑一棵树的情况，随机钦点一些点让其度数为奇，如果钦定点数为奇，由握手定理显然方案数为 $0$；否则删边方案是唯一的。

证明：考虑数学归纳法，$n=1$ 时显然，$n > 1$ 时找到一个叶子节点，根据钦定情况删掉或不删与其相连的边，题目就转化为了 $n-1$ 的情况。

考虑连通图的情况，随便建一颗 dfs 生成树，确定非树边的删边方案和哪些点度数为奇后，树边的删边方案也是唯一的，证明同上。（如果钦定点数为奇方案同样为 $0$）

因此对于每个连通块，设有 $x$ 个点，$y$ 个非树边，则令 $i$ 个点度数为奇的方案数为 $[i \bmod 2 = 0]2^y\dbinom{x}{i}$。

对于非连通图，对每个连通块处理后 $O(n^2)$ 背包 dp 即可。

ARC115E¶

题意¶

构造一个长度为 $n$ 的序列，第 $i$ 个数可以选取 $[1,a_i]$ 中的任意一个整数，求相邻数均不相同的方案数。($2 \leq n \leq 5 \times 10^5$，$1 \leq a_i \leq 10^9$)

题解¶

先离散化，得到 $m$ 个区间。设 $f_{i,j}$ 为前 $i$ 个数已经确定，最后一个数落在第 $j$ 个区间的方案数。

设第 $i$ 个数可以选取离散化后的第 $1$ 到 $b_i$ 个区间，则当 $j > b_i$ 时有 $f_{i,j} = 0$；当 $j \le b_i$ 时，有： $$ f_{i,j} = l_j\left(\sum_{k=1}^m f_{i-1,k}\right)-f_{i-1,j} $$ 其中 $l_i$ 表示第 $i$ 个区间的长度。考虑当这一个数为第 $j$ 个区间的每一个数时，上一位都不能是这个数，这些方案加起来恰好就是 $f_{i-1,j}$，因此要将其减去。

令线段树每个叶节点均有一个权值 $l_i$，上传后每个区间都有一个权值，即对一个区间加 $i$ 相当于加 $ij$，其中 $j$ 是该区间的权值。同时支持区间加与区间乘，操作时先得到总体的和 $x$，再将 $[b_i+1,m]$ 全部乘 $0$，将 $[1,b_i]$ 全部乘 $-1$ 后区间加 $x$ 即可。

总时间复杂度为 $O(n \log n)$。