做题记录 - 洛谷保存站

[cnblogs](https://www.cnblogs.com/caoshurui/p/18042065)

用来记录在做题时遇到的一些有意思/看了题解才做出来的题。

## [Reachability from the Capital](luogu.com.cn/problem/CF999E)

首先，如果一个点本来就可以被 $s$ 点到达，那么可以直接在图中删去。

考虑剩下的点。

我们对每个点求出其能到达那些点，然后按能到达的点的数量从大到小排序，再依次删去这些点（每次删完要把这个点能到达的点删去，因为其已经和 $s$ 联通），统计答案。

删去一个点不用真的把它干掉，打个标记即可。

[code](https://www.luogu.com.cn/paste/0fjwxt48)

## [Tree with Small Distances](luogu.com.cn/problem/CF1029E)

又是一道不会做的图（树）上问题，看来找时间得补补。

考虑贪心的去选择一个点连边。
很自然的可以想到选择离根最远的那个点，然后连边。

但思考后可以发现这样并不是最优的，如图。

![](https://cdn.luogu.com.cn/upload/image_hosting/pjp4vgdq.png)

红色节点是我们要连接的点。

如果我们连接了 $rt$ 和红色节点，那么我们就要连两条边，方案如下（蓝色是新连的边）：

![](https://cdn.luogu.com.cn/upload/image_hosting/hdxbas5w.png)

然而可以发现，如果我们连接红色节点的父亲节点显然只要一条边。

那么我们就可以找到一个离红色节点最远的点，使得这个点与红色节点的距离不超过 $1$（因为到达那个节点还要走一条边）。

那么就有两种方法连接，要么连接其父亲节点，要么连接儿子节点。
但由于我们是按深度从大到小选择，所以其儿子一定是合法的了。
所以我们直接连接父亲节点就好了。

在连接完节点后要把其和与其相邻的点标记，不再操作（因为这些点已经合法）。

[code](https://www.luogu.com.cn/paste/s800586w)

## [Fake Plastic Trees](luogu.com.cn/problem/CF1693B)

~~干脆改成图树选讲得了~~

对于每一个点，显然有一种最优的策略，那就是我们让这个点的 $a$ 值最大（前提条件是操作次数要最少）。
因为这样能给其祖先节点带来更多的选择方式。

那么考虑一个点其能获得的在操作次数最少的情况下是多少。
首先，其子节点的 $a$ 的和是肯定可以得到的，然后分类讨论一下两种情况：

1. $a_u<l_u$：对于这种情况，显然需要对该节点额外进行一次操作，那么答案增加，且将 $a_u$ 改为 $r_u$（反正都花代价了，为什么不选一个最好的呢？）

2. $l_u\le a_u$：对于这种情况，我们需要判断其值有没有超过 $r_u$ 如果超过了就设为 $r_u$。

[code](https://www.luogu.com.cn/paste/4g1otwhq)

## [水の数列](https://www.luogu.com.cn/problem/P5012)

一个很妙的题，还是写一下吧。

（由于该问题需要化简，所以就从题目背景中的题来讲吧）

### 问题 1：

贪心水题，题目中有做法了。

### 问题 2：

考虑到值域只有 $10^6$，那么枚举 $x$ 然后暴力给区间打标记。

但这样就变成 $10^6n$ 了（离散化后是 $n^2$，但 $n$ 有 $10^6$ 没影响）。

考虑如何快速的维护区间。

不难想到，我们从小往大枚举 $x$ ，然后把与 $x$ 相同的数在序列中标记，那么每次我们都会加入一些数。
然后用并查集维护，将区间看作一个集合。

因为要求平方和，所以还要维护并查集每个节点的子树大小。
每次合并计算代价。

代价的增量（$d$ 数组存的是子树大小，$x$ 是合并后的父亲节点，$y$ 是合并后的子节点）：

$$(d_x+d_y)^2-(d_x)^2-(d_y)^2$$

~~虽然没必要化简但还是化简一下吧~~

$$=(d_x)^2-(d_x)^2+(d_y)^2-(d_y)^2+2d_xd_y$$

$$=2d_xd_y$$

时间复杂度：$\operatorname{O}(V\log n)$（当然可以加个按秩合并）

### 问题 3：

我们在并查集的过程中另外用一个变量计算段数，然后找到段数在 $l$ 到 $r$ 中的最大值即可（具体维护方法就是每次将一个数标记为可行就加 1，合并两个集合就减 1）。

时间复杂度：$\operatorname{O}(V\log n)$

### 问题 4：

有 $T$ 组询问，所以开桶把每个段数的最大答案存下来。
然后维护区间 RMQ。（由于要输出方案，所以要把 $x$ 与代价捆绑）

用 ST 表 / 线段树会被卡空间。
由于 $T$ 很小，直接用莫队或分块。

时间复杂度：$\operatorname{O}(V\log n+T\sqrt{V})$

### 问题 5：

不能离线了，所以不能用莫队。
但还是可以用分块。

时间复杂度：$\operatorname{O}(V\log n+T\sqrt{V})$

[code](https://www.luogu.com.cn/paste/amv22i2j)

## [[yLOI2019] 梅深不见冬](https://www.luogu.com.cn/problem/P5521)

贪心好题。

考虑对于每个节点计算代价。

有个显然的贪心策略：**当前节点的子节点在当前节点放了数时就可以全部取消掉了。**

那么我们就得到了答案的第一种来源：**当前节点的权值加上其所有子节点的权值。**

然后考虑最大值出现在给子节点放数的时候。

由于前面放的子节点的数当前还不能取消，所以第 $i$ 个儿子在放置过程中的最高代价是：

$$\sum_{j=1}^{j<i}a_{id_j}+ans_{id_i}$$

然后我们考虑如何安排子节点的顺序。

**假设我们已经确定了前 $i$ 个节点的顺序，考虑接下来 $x$ 和 $y$ 那个节点更优。**

这样不好分析，所以我们设 $x$ 要优于 $y$ （很多题目都是这样证明的）。

令 $sum=\sum_{j=1}^{j<i}a_{id_j}$，那么当 $x$ 优于 $y$ 时，以下不等式成立：

$$sum+a_x+ans_y<sum+a_y+ans_x$$
$$a_x+ans_y<a_y+ans_x$$
$$ans_y-a_y<ans_x-a_x$$

所以我们把子节点按照 $ans_x-a_x$ 从大到小排序，依次计算即可。

[code](https://www.luogu.com.cn/paste/o3l2yd2n)

## [[六省联考 2017] 组合数问题](https://www.luogu.com.cn/problem/P3746)

很好的矩阵乘法题。

首先众所周知组合数是可以用递推来求的。
设 $f_{i,j}=C_i^j$，则有：

$$f_{i,j}=f_{i-1,j-1}+f_{i-1,j}$$

边界条件为 $f_{i,0}=1  (1\le i\le n)$。

这题中要我们求的是$\sum_{i = 0}^\infty C_{nk}^{ik + r}$，所以相当于求 $\sum_{i = 0 \wedge i \equiv r(mod _k)}^{nk} C_{nk}^{i}$，所以设 $f_{i,j}$ 表示 $\sum_{s = 0 \wedge s \equiv j(mod _k)}^{i} C_{i}^{s}$，则有：

$$f_{i,j}=f_{i-1,j}+f_{i-1,j-1+(j-1\le0)\times k}$$

那么答案就是 $f_{nk,r}$。

但是考虑到 $n$ 很大，直接递推显然超时，但 $k$ 和 $r$ 很小，所以直接矩阵乘法优化一下就好了。

为了方便，可以把矩阵的下标从 $0\le i<k$ 偏移成 $1\le i\le k$。

[code](https://www.luogu.com.cn/paste/nqq4j4og)

## [Squirrel Migration](https://www.luogu.com.cn/problem/AT_arc087_d)

首先有一个 trick：如果要让距离和最大，那么以重心为根，每个点都只会往重心的另外一个子树中的点匹配。

证明：

1. 每个点是否可向外匹配：

根据重心的定义，每个子树大小都是小于等于 $\frac{n}{2}$ 的，所以除了该子树中的点剩下的点数量是大于等于 $\frac{n}{2}$，所以一定是可行的。

2.如果不这样进行匹配是否不会更劣

如果有点向同一个子树内的点匹配，可以让每对中的一个点向另外一对中的一个点匹配，这样答案至少会增加 $4$，所以不这样匹配一定更劣。

那么我们就可以把所有子树的大小拿出来做 dp 了。

直接 dp 显然不好写，考虑容斥。

设 $f_{i,j}$ 表示前 $i$ 个子树有 $j$ 个点向自己子树内匹配，那么有转移方程：

$$f_{i,j}=\sum_{k=0}^{j} f_{i-1,j-k} \times (C_{a_i}^k)^2$$

其中 $a_i$ 是当前子树大小。

那么根据二项式反演，答案就是：

$$\sum_{i=0}^n (-1)^i \times (n-i)! \times f_{c,i}$$

其中 $c$ 是子树个数。

[code](https://atcoder.jp/contests/arc087/submissions/51721121)

## [Sequence of Substrings](https://www.luogu.com.cn/problem/AT_abc240_h)

看到这题首先有个很显然的 dp：$f_{i,j}$ 表示当前最后一个区间为 $[i,j]$，最多选了多少区间。那么有转移：

$$f_{i,j}=max_{1\le k\le l < i, s[k,l]<s[i,j]} f_{k,l}+1$$

这样是 $\operatorname{O}(n^4)$ 的，无法通过。

我们先不考虑优化复杂度，而是先优化一下 dp 的方式。

我们可以把所有串都拿出来，然后按照字典序排序。这样对于每个字符串，我们找到其前面一个不等于它的串，并且这个串在原串的位置也要在它前面，然后进行转移。这时我们可以用线段树维护每个串结尾的位置对应的 dp 最大值，优化转移。

此时转移的复杂度已经较低了（虽然仍然无法通过），我们考虑优化这个排序。

排序本身很难优化（最多也只能用二分+hash优化到 $\operatorname{O}(n^2log^2n)$），所以我们考虑用某些东西替代排序。

不难想到我们可以用字典树！（下文中该节点对应字符串是指从根节点到当前节点路径上的字符连接）由于是 01 串，所以只有两个儿子。画个图不难发现该节点对应字符串字典序要小于左儿子的字符串的字典序，而左儿子对应字符串字典序要小于右儿子的字符串的字典序，所以我们先对当前点进行转移，然后递归处理左儿子，最后处理右儿子。

现在时间复杂度是 $\operatorname{O}(n^2\log n)$ 的了，但依旧无法通过，原因是我们现在字符串的个数就有 $\operatorname{O}(n^2)$ 个。考虑如何让字符串个数减少。

**结论 1：如果选择的后一个字符串比当前结尾的字符串长，那么其长度与当前结尾的字符串的长度之差不会超过 1**

**证明：**

考虑如果有一个字符串长度比前一个字符串多 2 会怎么样。

不难发现，此时我们将这一个字符串的最后一个字符删掉该字符串也是比前一个字符串的字典序大的，而这样显然不会让答案变小（甚至可能变大）。

**结论 2：一定有一种合法的选择方法使得答案最大且选择的字符串的长度均小于等于 $\sqrt{2n}$。**

**证明：**

在结论1的条件下，如果我们想要最长的串长度最大，那么长度选出的串的长度肯定是 $1,2,3...... x$ 每次加一，那么字符串的长度和就是 $\frac{x\times (x+1)}{2}$，由于字串之间不能相交，所以 $x\le \sqrt{2n}$。

有了结论 2，我们就有了一个很强的优化：枚举长度小于等于 $\sqrt{2n}$ 的字符串，然后进行 dp。这样时间复杂度是 $\operatorname{O}(n\sqrt{n}\log n)$ 的，瓶颈在于 dp 转移时的线段树优化。

[code](https://atcoder.jp/contests/abc240/submissions/53679590)

## [CF1537F](https://www.luogu.com.cn/problem/CF1537F)

一道结论型的图论题。

### 约定：

偶环：节点个数为偶数的环使得任意不相同两点之间有且仅有 2 条简单路径的环。

奇环：节点个数为奇数的环使得任意不相同两点之间有且仅有 2 条简单路径的环。

令点 $i$ 的权值为 $a_i$，有 $a_i=t_i-v_i$，其中 $v_i,t_i$ 为题目给出的。

称一个图为好的当且仅当这张图是否可以在有限步操作中，使得每个节点满足 $a_i=0$。

### 基础结论：

**结论 1：对于一个偶环，这个偶环是好的当且仅当将其黑白染色后所有黑点的权值和等于所有白点的权值和。**

**证明：**

染色后每个黑点想要使自己点权变化那么左右的其中一个白点也会变化，所以黑、白点权值之和的差值不变。要使得最后权值都为 0，那么黑、白点权值之和必须相等。

对于这个结论，还有一个小推广：该结论对于所有二分图都有效，证明过程类似。

**结论 2：对于一个奇环，这个奇环是好的当且仅当其点权之和是偶数。**

**证明：**

对于一个奇环，两点间的两条路径长度一定一个是奇数一个是偶数，那么如果有两个点要同时操作，就找到长度为奇数的那条路然后一加一减即可，如图：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240617220614540-1161263722.png)

这个结论对奇环上挂了树同样适用。

### 一般性的结论

前面考虑了一个环的情况，现在考虑更一般性的，也就是两个环，或环上挂了树。

两个环有以下三种大致状态：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240617221215373-58402815.png)

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240617221356756-1739836257.png)

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240617221436604-1467541819.png)

下文只考虑第三种，事实上这三种不同形态推导结论的方式是类似的。

#### 1. 两个偶环相接

如图：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240618141942359-1884745639.png)

由于两个偶环接在一起是一个二分图，根据基础结论 1 的小推广，该图可以视作偶环。

#### 2. 偶环与奇环相接

如图：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240618142333452-2112102913.png)

考虑一种最基础的，这张图上只有两个点的权值为 1。

如果这两个点都在偶环上，那么可以从如下路线一加一减，得到答案：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240618142904129-373058840.png)

如果都在奇环上，那么直接就是结论 2。

如果一个在偶环上，一个在奇环上，那么把中间那条边删掉对答案没有影响，所以依旧是结论 2。

综上所述，偶环与奇环相接的情况就相当于奇环。

#### 3. 奇环与奇环相接

如图：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240618143306435-1190445008.png)

依旧考虑这张图上只有两个点的权值为 1。

如果两个点在同一个奇环上，那么就是结论 2。

否则，如下图：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240618143525079-178744667.png)

由于环大小是奇数，所以将中间那条边经过一个奇环但不走中间的边的路径长度是偶数的，而经过中间的边路径长度是奇数（也就是 1），所以这两点之间一定有一条长度为奇数的路径，在这条路径上操作即可，如图：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240618143903436-1237793683.png)

综上所述，两个奇环相接的情况就相当于奇环。

#### 4. 环上挂树

此时我们只要考虑奇环的情况，因为偶环在此时是二分图。

如图：

![](https://img2024.cnblogs.com/blog/3397709/202406/3397709-20240618212647132-211270256.png)

我们可以从树的叶子节点开始，不断向上进行修改，将所有权值转移至环上，然后就是结论 2。

**综上所述，如果一个图中包含奇环，那么就可以视作奇环，否则视作偶环。**

### 实现

用 `Tarjan` 求一个生成树，然后对于每条返祖边，看构成的环是否是奇环。或者直接黑白染色判断是否是二分图，如果是二分图就不存在奇环。

## [[NOIP2022] 建造军营](https://www.luogu.com.cn/problem/P8867)

不难发现，只有割边被炸才会导致两个关键点无法互相到达。所以我们可以直接把边双连通分量缩在一起。

缩完之后这张图就会变成一棵树。

考虑在这棵树上做dp。

定义 $f_{i,0}$ 表示在 $i$ 的子树中没有出现关键点，$f_{i,1}$ 表示在 $i$ 的子树中出现了至少一个关键点。

但这样很容易重复，所以我们钦定 $(fa,i)$ 这条边一定不选。令 $c_i$ 表示第 $i$ 个边双内有多少条边，$cnt_i$ 表示有多少点，$s_i$ 表示这棵子树里有多少原图的边（包括边双内的）,这样答案就是 $\sum f[i][1]\times 2^{max(0, m - 1 - s_i)}$。（因为其它的边随便选不选）。

考虑转移，首先 $f_{u,0}$ 很好转移，转移如下：

$$f_{u,0}=2^{c_u}\times \prod\limits_{{i}\subseteq son_u} f_{i,0}$$

然后考虑 $f_{u,1}$，对于一个儿子 $v$，考虑一下两种情况：

1. 之前的儿子和 $u$ 都没有出现关键点

有：$f_{u,1}=f_{u,0}\times f_{v, 1}$

2. 之前的儿子或 $u$ 中出现了关键点

有：$f_{u,1}=f_{u,1}\times (f_{v, 1}+2\times f_{v,0})$

两种转移合并一下就好了，总时间复杂度为 $\operatorname{O}(n\log mod)$，预处理逆元可以做到线性。

[code](https://www.luogu.com.cn/paste/qui055ol)

## [[CTSC2018] 暴力写挂](https://www.luogu.com.cn/problem/P4565)

令 $dis(x,y)$ 为 $x,y$ 的距离，$dis(x)=dis(1,x)$。

首先这个答案代价很难计算，所以考虑进行一个式子的推：

$$原式=\frac{1}{2}(2\times dis(x)+2\times dis(y) - 2\times dis(Lca(x, y))- 2\times dis'(Lca'(x, y)))$$
$$=\frac{1}{2}(dis(x)+dis(y)+dis(x,y)-2\times dis'(Lca'(x,y)))$$

推成这样我们就可以开始考虑继续解题了。

首先我们对第一棵树做点分治，令当前根节点为 $rt$，定义 $T$ 中 $v_i=dis(rt)+dis(i,rt)$，那么我们就可以枚举 $Lca'(x,y)$，然后找到两个 $x,y$ 使得无论在那一棵树上以当前枚举的点为根它们都不在同一个子树内。

这个问题可以用 dp 解决。设 $f_{i,0}$ 表示 $T'$ 这棵树中 $i$ 子树内最大的 $v_i$ 对应的 $i$，$f_{i,1}$ 表示 $T'$ 这棵树中与 $i$ 不在第一棵树的同一个子树中 $v_i$ 最大的对应的 $i$。转移的时候枚举当前的两个状态和当前儿子的两个状态即可。

但这样复杂度是 $\operatorname{O}(n^2\log n)$ 的，无法通过。

但不难发现，其实我们所有 dp 中有用的点数量加起来是 $\operatorname{O}(n\log n)$ 级别的，所以可以用虚树对这个过程进行优化。

总时间复杂度 $\operatorname{O}(n\log^2n)$，瓶颈在于建虚树，不过对 $dfn$ 排序的时候可以使用 `stable_sort`降低常数。

[code](https://www.luogu.com.cn/paste/mde68kig)

## Nauuo and Pictures (hard version)

考虑 dp。

设 $f_{id,i,j}$ 表示对于第 $id$ 张图片，现在进行了 $i$ 次操作，其中 $j$ 次是将某数加一，权值的期望值。 $\operatorname{O}(1)$ 转移是简单的。

这样时间复杂度是 $\operatorname{O}(nm^2)$ 的，考虑优化。

考虑将每个照片拆成 $w_i$ 个同类的且权值为 $1$ 的照片，那么现在照片就只有两种：$a_i$ 等于 $1$  或 $a_i$ 等于 $0$。

那么就可以将 $id$ 那一位去掉。 设 $f_{i,j}$ 表示进行 $i$ 次加一操作，$j$ 次减一后的期望代价，有转移：

$$f_{i,j}=f_{i-1,j}\times \frac{i+\sum_{k=1}^{n}{w_k[a_k=1]}}{i-j+\sum_{k=1}^{n}w_k}$$
$$f_{i,j}=f_{i,j-1}\times \frac{\sum_{k=1}^{n}w_k[a_k=0]-j}{i-j+\sum{k=1}^{n}w_k}$$

这样时间复杂度是 $\operatorname{O}(m^2\log m)$，可以通过本题，但预处理逆元可以做到 $\operatorname{O}(m^2)$。

## Anticube

首先有个想法：对每个 $a_i$ 分解质因数，然后用 $map$ 找到与之冲突的数，取两者中间出现最多的数。

但这样是 $\operatorname{O}(n\sqrt{a_i})$ 的，无法通过。（不过好像可以 BSGS？

考虑优化：首先可以先将 $\sqrt[3]{a_i}$ 内的质因数先除掉，这样是可以实现的。

那么剩下的数就一定是一下几种形式：$p^2$，$pq$ 和 $p$。

首先考虑剩下的是 $p^2$，那么直接开根就行。

如果剩下的是 $pq$，那么想要与它凑成完全立方数就只能含有 $p^2q^2$，但 $p,q$ 都是大于 $3000$ 的整数
，所以 $pq>10^{10}$，直接将答案加一，不要放进 $map$。

剩下 $p$ 同理。

那么这样我们就以 $\operatorname{O}(n\sqrt[3]{n})$ 解决了这道题。

PS:为了防止类似 ```abs((__int128)x)``` 之类的悲剧发生，这边建议手写 $\log V$ 的开根。（虽然这题没有涉及 __int128，但有精度问题的函数少用）。

## Minimum Sum of Maximums P

首先考虑把这个奇怪的贡献拆一下，可以拆成：$\sum_{i=1}^{n-1}{\frac{a_i+a_{i+1}+|a_i-a_{i+1}|}{2}}$。

为了避免一些奇怪的边界，我们在序列左右插入一个极大值，最后减去即可。

考虑到 $a_i+a_{i+1}$ 是固定的，所以我们要最小化 $\sum_{i=1}^{n-1}{|a_i-a_{i+1}|}$。

设区间左边那个固定点值为 $x$，右边那个值为 $y$，若 $x\le y$，那么直接将这段数从小到大排序一定不会更劣。类似的，如果 $x>y$，那么可以直接从大到小排，证明显然。

对于一段区间，设该区间的最大值为 $M$，最小值为 $m$，那么该区间的代价是：

$$|L_i-m|+M-m+|R_i-M|$$

（其中 $L_i$ 和 $R_i$ 是这段区间左右固定的数的值）

那么我们现在的任务就是分配每一段的最小值和最大值。

#### 结论：对于两段编号为 $i,j$ 的区间，这两段区间的值域要么完全包含，要么没有相交。

直接反证是比较简单的。

那么我们就可以设计状态，设 $f_{l,r,s}$ 表示当前值域区间为 $[l,r]$，已经固定了的区间集合为 $s$，那么有转移：

1. 没有值域恰好为 $[l,r]$ 的区间：$f_{l,r,s}=\min{f_{l+1,r,s},f_{l,r-1,s}}$

2. 将两段拼起来，设 $len_i$ 集合为 $i$ 的段的长度和，有：$f_{l,r,s}=\min{f_{l,l+len_T-1,T}+f_{l+len_T,r,s-T}}$。

3. 正好有 $[l,r]$ 的区间：$f_{l,r,s}=\min{f_{l+1,r-1,s-{x}}+Calc_x{l,r}}$，其中 $Calc_x{l,r}$ 是第 $x$ 段值域为 $[l,r]$ 时的代价。

这样时间复杂度是 $\operatorname{O}(3^kn^2)$ 的，瓶颈在第二个转移。

## [[ABC305Ex] Shojin](https://www.luogu.com.cn/problem/AT_abc305_h)

首先考虑如果只能分一段，怎样排列是最优的：

> 首先如果 $a_i=1$，那么肯定是将 $i$ 放在最后面。
> 接着设现在有两个数 $i$，$j$，且 $i$ 放在前面比 $j$ 放在前面优，此时满足什么性质。
> 可以得到 $i$ 放在前面的代是：$a_j(a_i x+b_i)+b_j$，$j$ 放在前面的代是：$a_i(a_j x+b_j)+b_i$。
> 那么此时有： $$a_j(a_i x+b_i)+b_j\le a_i(a_j x+b_j)+b_i$$
> 化简一下：$$a_ia_jx+a_jb_i+b_j\le a_ia_jx+a_ib_j+b_i$$
> 最终得到：$$\frac{b_i}{a_i-1}\le \frac{b_j}{a_j-1}$$
> 因为已经判掉了 $a_i=1$，所以可以直接除。

接着考虑计算答案。设 $f_{i,j}$ 表示前 $i$ 个数分成了 $j$ 段代价的最小值，有转移：

$$f_{i,j}=min(f_{k,j-1}+F(k+1,i))$$

其中 $F(k+1,i)$ 是区间 $\left[k+1,i\right]$ 的代价。

这样复杂度是 $\operatorname{O}(n^3)$ 的，无法通过。

考虑优化。首先先把 $a_i=1$ 全部删掉，因为这些数的贡献都是 $b_i$，最后加上即可。

这时可以发现，我们选择的每一段的长度最多是 $\operatorname{O}(\log_2 X)$ 级别的。因为此时所有的 $a_i>1$，且$b_i\ge 1$，所以如果选择了长度为 $x$ 的区间，那么这个区间的值至少是 $2^{x-1}$。

那么就可以处理所有长度小于等于 $\log x$ 的区间的代价，每次转移时也只枚举最近的 $\log x$ 个位置，暴力转移即可。

此时时间复杂度降到了 $\operatorname{O}(n^2\log x)$

那么现在优化方向只能放到第二维上了。

一种显然的方法是二分最少需要多少段，然后用 wqs 二分去限制段的数量，进行 dp。时间复杂度 $\operatorname{O}(n\log^3 X)$，也许可以通过（？

但实际上我们并不需要二分最少需要多少段。直接用 wqs 二分。对于一个代价 $c$，每增加一段代价增加 $c$。如果代价为 $c$ 时最后的答案小于等于 $X$，那么就往大的数找，否则往小的数找。要注意如果转移的值相同要优先选段数最大的（这样能让最终实际的代价最小），然后如果二分出的 $x$ 对应的 $f_n$ 比 $m$ 小，就可以进行调整，将段数减少 $1$ 并且让 $f_n$ 增加 $x$。

最后特判一下所有 $a_i$ 都等于 $1$ 的情况。

[code](https://atcoder.jp/contests/abc305/submissions/56734607)

## [[北大集训 2021] 简单数据结构](https://www.luogu.com.cn/problem/P8987)

大大大大大ds。

首先考虑考虑最开始所有的 $a_i$ 都为 $0$ 时怎么做。

那么此时 $a$ 是单调不降的，用线段树维护区间和区间最大值并支持对 $a_i$ 加上 $i$，每次 `checkmin` 就是把一段后缀赋值成某一个数，至于后缀位置就是从后往前最后一个大于操作给出的 $x$ 的位置，在线段树上二分即可。

接着考虑如果 $a_i$ 最开始不等于 $0$ 怎么办。

不难发现，那些受到操作 $1$ 影响的数一定是递增的，而没有受到操作 $1$ 影响的数可以被表示成 $a_i+k\times i$（其中 $k$ 是操作 $2$ 的次数），所以考虑把这 $n$ 个数分成受到操作 $1$ 影响和没有受到操作 $1$ 影响两个部分，设没有被影响的集合为 $S$，被影响的集合为 $T$，用线段树维护即可。

那么现在的问题是如何在 $checkmin$ 的时候把 $S$ 中的一些元素快速的丢到 $T$ 里去。

考虑哪些要从集合 $S$ 丢到 $T$ 中的数满足什么性质。令当前操作 $2$ 此时为 $k$，不难发现这些数要满足 $a_i+k\times i\geq c$，移项可以得到 $a_i\geq c-k\times i$。这相当于要将一个半平面内的数从 $S$ 丢到 $T$，如图：

![](https://cdn.luogu.com.cn/upload/image_hosting/8a9r48w3.png)

这些红色的点就是需要移除的。

考虑分块凸包。把每个数看作一个点 $\left(i,a_i\right)$，然后分成 $\sqrt{n}$ 个块。每个块内建立一个下凸壳，每次暴力在凸壳上找到一个点使得 $y\geq k\times x+b$（$k$ 在本题中是当前操作 $2$ 的个数的相反数，$b$ 是 `checkmin` 时题目给出的 $x$），然后把这个点删掉。删掉后可以直接暴力重构凸壳。这样子每次删掉一个点复杂度是 $\operatorname{O}(\sqrt{n})$ 的（因为已经满足 $x$ 递增了，不需要排序），一个点只会被删 $1$ 次，所以这部分的时间复杂度是 $\operatorname{O}(n\sqrt{n})$ 的。删除的时候可以双指针做（每次删点不要重新从凸壳的第一个点开始遍历，直接从被删除的点的前一个开始），但其实直接从头遍历好像复杂度也是对的（？

由于 $T$ 中不一定包含所有数，所以线段树要记录每个位置上的数有没有加入 $T$，记录的信息只记录已经加入了 $T$ 的那些数。集合 $S$ 可以用树状数组维护，因为只要维护第 $i$ 个位置是否存在 $S$ 中，然后每次找到在分块凸包中被删除的数单点修改。

总时间复杂度 $\operatorname{O}(n\sqrt n)$

代码比较复杂，细节比较多，要稍微注意一下线段树下传 `tag` 时加法和赋值的顺序以及对区间最大值和区间和的影响。

[code](https://www.luogu.com.cn/paste/2rdlpzfj)

## [P5064 [Ynoi2014] 等这场战争结束之后](https://www.luogu.com.cn/problem/P5064)

个人感觉比较友好（？的一道 Ynoi。

首先操作 2 非常难受，所以直接根据操作建一棵树，那么就可以通过遍历这个树来完成回退操作了。

维护连通块可以使用并查集，而查询区间第若干大可以用分块。分块记录某个块内以某个点为根有多少点，合并两个联通块时直接暴力把分块的每个块加上，撤回时同理。

这样空间是 $\operatorname{O}(n\sqrt{n})$ 的，无法通过，考虑优化。

由于该算法常数较小，所以时间上有很大的余地，所以可以调大块长始块数变少。实测 $d=2\times 10^3$ 最好。

此时只有 24 分，但是记录块内信息的数组的值不会很大，所以可以直接用 `short`。

这样有 88 分，最后用 `inline` 优化一下，然后选择一个较好的语言即可通过。

最后注意一下并查集因为要撤回所以不能路径压缩，要启发式合并。

[code](https://www.luogu.com.cn/paste/62epquuj)

## DZY Loves Math

![](https://img2024.cnblogs.com/blog/3397709/202409/3397709-20240926201639474-2079714992.png)

$$1\le N,M\le 10^6,1\le T\le 10^4$$

进行一个式子的推：

$$\sum_{i=1}^{n}\sum_{j=1}^{m} f(\gcd(i,j))$$
$$=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{n}\sum_{i=1}^{m}f(d)\times [\gcd(i,j)=d]$$
$$=\sum_{d=1}^{\min(n,m)}f(d)\sum_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor}[\gcd(i,j)=1]$$
$$=\sum_{d=1}^{\min(n,m)}f(d)\sum_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{d}\right\rfloor}\sum_{d'|i,d'|j}\mu(d')$$
$$=\sum_{d=1}^{\min(n,m)}f(d)\sum_{d'=1}^{\left\lfloor\dfrac{\min(n,m)}{d}\right\rfloor}\mu(d')\times \left\lfloor\dfrac{n}{d\times d'}\right\rfloor \times \left\lfloor\dfrac{m}{d\times d'}\right\rfloor$$

令 $s=d'\times d$。

$$原式=\sum_{s=1}^{\min(n,m)}\left\lfloor\dfrac{n}{s}\right\rfloor\times \left\lfloor\dfrac{m}{s}\right\rfloor \sum_{d|s} f(\frac{s}{d}) \mu(d)$$

$\mu$ 函数可以通过线性筛进行预处理，考虑怎么处理 $f$ 函数。考虑线性筛在筛质数时筛的方式是每次找到最小质因子，所以记录当前的最小质因子和最小质因子的次数和 $f$ 的值，转移时更新即可。然后枚举每个 $\mu$ 不为 0 的数，更新其每个倍数的值。
 
最后对 $s$ 进行整除分块，时间复杂度 $\operatorname{O}(n\log n+T \sqrt{n})$，不过预处理只要考虑 $\mu$ 不为 0 的数，所以跑不满。

[code](https://www.luogu.com.cn/paste/nv1jobgz)

## [[AGC064C] Erase and Divide Game](https://www.luogu.com.cn/problem/AT_agc064_c)

首先考虑数的数量很少可以一个个加入该怎么处理。考虑删除一个所有的奇数或偶数并且将剩下数除以 2 会产生什么影响。考虑将一个数从最低位向最高位插入 trie 树中。那么每一次操作对应的影响就是向左儿子/右儿子走一步。所以将每个数都插到 trie 中，那么一个人输了就是到达了一个空子树。在 trie 上做 dp 即可。

考虑区间长度很长的情况下该怎么优化。考虑将区间 $[l,r]$ 分解成若干个 $[x,x+2^d)$ 的区间，那么每个区间内的所有数插入到 trie 中对应的就是一个大小为 $2^d$ 的完美二叉树，下面接着一条链。而链的数量暴力插入是可以接受的，考虑优化掉完美二叉树的插入。

考虑建 $60$ 棵 trie，第 $i$ 棵 trie 表示这个完美二叉树的大小 $2^i$。那么长度为 $2^i$ 的区间就插入第 $i$ 棵 trie 中。

考虑在这 $60$ 棵 trie 上进行 dp。设 $f_v$ 表示在这 $60$ 个 trie 上第 $i$ 个 trie 上当前这个位置为 $v_i$。转移时将每个点向左儿子或右儿子移动即可。

实现时对于第 $i$ 棵 trie 先构建一条长度为 $i$ 的链。

时间复杂度按照实现方式为 $\operatorname{O}(n\log^2 n)$ 到 $\operatorname{O}(n\log^3 n)$。

[code](https://www.luogu.com.cn/paste/fkkp02sx0)

## [[AGC063C] Add Mod Operations](https://www.luogu.com.cn/problem/AT_agc063_c)

首先考虑如何判断无解。对于一对 $i,j$，如果 $a_i=a_j$ 且 $b_i\neq b_j$ 那么就一定无解，否则一定有解。

对于 $a,b$ 都相同的一对数，可以只考虑一个位置，所以可以对原数组去重。然后按照 $a$ 排序。

考虑选择了一对 $x,y=x+\max a$ 进行操作会对序列产生什么影响。将所有数放在数轴上，如图（借用了 at 的官方题解的图）：

![](https://img.atcoder.jp/agc063/dc0563aebbb5cc324533f63ea6b6ab2e.png)

相当于是把从 $a_n$ 到 $y$ 这条线段移动到了整体的前面。

通过若干次平移可以得到如下形式：

![](https://img.atcoder.jp/agc063/1ea711aa697931f331e49fb934033aad.png)

如上图，有 $a_2=0,a_i=a_{i-1}+x_{n-i+2},a_1=a_n+x_1$，所以现在的目标是构造出 $x$，使得所有的 $a_i=b_i$。

首先有 $a_2$ 是等于 $0$ 的，这显然不符合要求，所以最后可以进行一次 $x=b_2$，$y=2\times 10^9$ 的操作，那么现在要让所有的 $a_i=b_i-b_2$。

考虑到 $a_i=a_{i-1}+x_{n-i+2}=b_i-b_{i-1}$，所以 $x_{n-i+2}=b_i-b_{i-1}$。然后考虑第一次操作要减去 $[0,a_1]$ 这一段，所以 $X=b_1-b_m-a_1$。

[code](https://atcoder.jp/contests/agc063/submissions/58560025)

## [[AGC064D] Red and Blue Chips](https://www.luogu.com.cn/problem/AT_agc064_d)

神仙找性质数数。感觉题解有些地方没太写清楚，这里稍微补充一些。

考虑校验答案序列的合法性。首先 ```R``` 和 ```B``` 的数量显然要和原串一致，接着考虑反向进行操作，在原串中从后往前遍历，维护当前字符串集合。

从第 $n$ 位开始，如果第 $s_i=$ ```R```，那么直接将当前的所有字符串中找到任意一个开头为 ```R``` 的字符串将开头的字符移除（如果找不到 ```R``` 开头的串就说明该答案串不合法）。否则如果 $s_i=$ ```B```，那么可以将当前的字符串集合中在原串中的任意一个串分成**两个以 ```B``` 结尾的分裂前的串的前缀和后缀**，塞入当前的字符串集合中。

> 考虑模拟对原串为 ```RBBRRB```，答案串为 ```RRBRBB``` 进行如上操作。
>
> $i=6$ 时，原串分裂成 ```RRBRB``` 和 ```B```，由于原串以 ```B``` 为后缀，删除 ```B```。
>
> $i=5$ 时，$s_i=$ ```R```，将 ```RRBRB``` 开头的 ```R``` 删去，此时字符串为 ```RBRB```。
>
> $i=4$ 时，$s_i=$ ```R```，将一个 ```RBRB``` 最开头的 ```R``` 删去，答案串变为 ```BRB```
>
> $i=3$ 时，$s_i=$ ```B```，对字符串分裂成 ```B``` 和 ```RB```，由于原串以 ```RB``` 为后缀，所以删除 ```RB``` 中的 ```B```，变为 ```R```。
>
> $i=2$ 时，$s_i=$ ```B```，删除 ```B```，此时还剩下 ```RB```。
>
> $i=1$ 时，$s_i=$ ```R```，删除字符串 ```R``` 此时，集合为空，说明该答案串合法。

分析一下我们操作的过程，每次遇到 ```R``` 的操作显然删除任意一个开头的 ```R``` 都是一样的，但遇到 ```B``` 的时候分裂的方式会影响最终的结果。由于可以任意进行分裂，而不合法情况是由开头的 ```R``` 决定的，所以分裂时会选择可以分裂出的 ```R``` 最多的方案。

令 $a_i$ 表示答案串中第 $i$ 个极长 ```R``` 连续段的长度，$k$ 表示答案串中有多少极长```R``` 连续段，$b_i$ 表示**将原串 $\operatorname{reverse}$ 后第 $i$ 个极长 ```R``` 连续段的长度**，$v$ 表示原串中的极长 ```R``` 连续段个数。于是在同满足如下条件时合法：

1. $\sum_{i=1}^{k} a_i=\sum_{i=1}^{v} b_i$

2. $a_1\ge b_1$

3. 将 $a_{2},a_3,a_4 \cdots a_k$ 从大到小排序，有：$\forall x,\sum_{i=1}^{x}a_i\ge \sum_{i=1}^{x} b_i$。

这个式子当时想了很久才想明白，所以稍微解释一下。

要从大到小排序是因为每次分裂时可以选择让 ```R``` 的数量尽量的多，但是由于开头的一段最开始就可以取出，所以 $a_1$ 不参与排序。$\forall x,\sum_{i=1}^{x}a_i\ge \sum_{i=1}^{x} b_i$ 是因为每次分裂后开头的 ```R``` 数量只有 $\sum_{i=1}^{x}a_i$ 个，而此时在操作中已经删除了 $\sum_{i=1}^{x}b_i$ 个 ```R```，所以如果答案序列要合法必须要满足当前所有分裂出来的字符串开头的 ```R``` 的数量足够进行操作。

那么现在问题就转化为了对 $a$ 数组计数（下文中的 $a$ 数组如果没有特殊说明指的都是去掉 $a_1$ 后的数组）。

首先对排序后的 $a$ 数组计数是简单的。但是因为可能会有相同的值，所以不能直接乘上 $(k-1)!$。假设去掉 $a_1$ 后有 $m$ 种数，第 $i$ 种数有 $c_i$ 个，那么这个排序后序列所对应的方案数为：

$$\dfrac{(k-1)!}{\prod_{i=1}^m(c_i!)}$$

由于 $(k-1)!$ 是固定，所以考虑对系数进行计算。

设 $f_{i,j,k}$ 表示当前最小值为 $i$，已经确定了 $j$ 个数，所有数的和为 $k$，所有满足该条件的系数之和。

拓扑序为 $i$ 从大到小（因为 $a$ 要从大到小排序）。

假设原串中 ```R``` 的个数为 $cnt$，有转移：

$$f_{i,j+l,k+l\times i}=\sum_{l=1,l\times i+k\le cnt}^{n-j} f_{i+1,j,k}\times \frac{1}{l!}$$

其中在从小到大枚举 $l$ 的过程中如果出现 $l\times i+k<a_{l+j}$ 就要退出循环不再进行转移（具体实现可以参考代码）。

这样做看起来时间复杂度是 $\operatorname{O}(n^4)$ 的，但是 $j,k$ 只有 $n^2$ 对，而 $i,l$ 的对数大概为 $\sum_{i=1}^{n}\frac{n}{i}$，这是调和级数，所以只有 $n\ln n$ 对。

因此总时间复杂度为 $\operatorname{O}(n^3 \ln n)$。

[code](https://atcoder.jp/contests/agc064/submissions/58579523)

## [[AGC062B] Split and Insert](https://www.luogu.com.cn/problem/AT_agc062_b)

考虑倒序进行处理，即把题目给出的的排列 $P$ 变为 $1,2,3,\cdots\cdots,n$，那么一次操作就成了从当前序列中取出 $k$ 个数插入到序列的最后面。

考虑到数据范围很小，所以大概率可以 dp。设 $f_{i,l,r}$ 表示操作了 $i$ 次，$\left[l,r\right]$ 这段值域对应的位置已经排好序。有两种转移：

1. 当前时刻不进行操作，那么直接从前一时刻继承，有：

$$f_{i,l,r}=f_{i-1,l,r}$$

2. 当前时刻会进行操作。由于只能选出一个子序列插到最后，所以当前这段排好序的区间只能从两个已经排好序的区间通过操作合并，有：

$$f_{i,l,r}=\min_{l\le x<r} f_{i-1,l,x}+f_{i-1,x+1,r}+(r-x)\times a_i$$

初始时对于每一对 $l,r$，满足 $l$ 到 $r$ 的数的位置有序，有 $f_{0,l,r}=0$。

总时间复杂度为 $\operatorname{O}(n^4)$。

[code](https://atcoder.jp/contests/agc062/submissions/58549602)

## [Beautiful Bracket Sequence (hard version)](https://www.luogu.com.cn/problem/CF1264D2)

一个序列的深度是子序列的最大值，所以考虑如何去确定这个最大值。

假设没有 ```?```，可以设 $f_i=\sum_{j=1}^{s_j=`(`}-\sum_{j=1}^{s_j=`)`}$，不难发现 $f_0<0$，$f_n>0$，而 $i$ 从 $0$ 到 $n$ 一定是在一直加一，所以找到 $f_i=0$ 的 $i$ 就是最佳决策点。所以如果序列中一共有 $y$ 个右括号，那么 一定有 $f_y=0$。所以只需要统计 $[y+1,n]$ 这个序列中的右括号个数即可得到该序列的深度。

所以我们可以在右括号和左括号之间统计贡献。对于 $s_i=$ ```?```，其只有在选择右括号时会产生贡献，并且所有右括号的数量之和要小于当前位置。如果一共有 $x$ 个问号，那么方案数为 $\sum_{j=0}^{i-y-2}\tbinom{x-1}{j}$。同理，如果一个位置为右括号，则贡献为 $\sum_{j=0}^{i-y-1}\tbinom{x}{j}$，这两个东西可以前缀和处理，总时间复杂度 $\operatorname{O}(n)$。

[code](https://codeforces.com/contest/1264/submission/283838540)

## [Move by Prime](https://www.luogu.com.cn/problem/CF653G)

首先考虑对于一个序列怎么计算。考虑到每次操作只能乘上或初除以一个质数，而最后如果数相等那么每个质数的出现次数一定相等。所以对于每个质数分开考虑，显然需要将每种质数的个数变成所有的该质数的出现次数的中位数。

那么对于一个序列，令质数 $p$ 的出现次数的中位数为 $v_p$，代价为：

$$\boxed{\sum_{p}\sum_{i,p|x_i} |cnt_{p,i}-v_p|}$$

由于 $cnt$ 数组是固定的，所以考虑每个数在系数为 $-1$ 和系数为 $1$ 时分别会作为子序列中的一个数贡献多少次，即可计算出结果。

于是考虑贡献该如何计算，对于当前计算的一个定值 $p$，$p$ 作为因子在这 $n$ 个数中的出现次数分别为 $c_1,c_2,c_3\cdots\cdots c_n$。对 $c$ 从小到大排序那么第 $i$ 个位置在所有子序列中系数的贡献就是：

$$\boxed{\sum_{j=i}^{n-1}\tbinom{n-1}{j}-\sum_{j=0}^{i-2}\tbinom{n-1}{j}}$$

其中 $j$ 是质因数 $p$ 出现次数比 $c_i$ 大的数选了的个数加上 $p$ 的出现次数比左边小的数的数中没有出现的数。

最终枚举 $p$，对所有 $c$ 排序，暴力算即可。不过有一些细节，比如说 $c_i=0$ 的数要特殊考虑一下。

总时间复杂度 $\operatorname{O}(n\log^2n)$，实际上根本跑不满。

[code](https://codeforces.com/contest/653/submission/283836733)

## [Weak Subsequence](https://www.luogu.com.cn/problem/CF135E)

一道很不错的数数题。

**结论一：如果存在一个长度为 $x$ 的弱字串，那么一定存在一个长度为 $x$ 的弱字串使得这个弱字串是由一个字符和一个长度为 $x-1$ 的字串组成的**。

考虑为什么是对的，观察下面一张图：（其中黑色是原串，红色是选出来的子序列，蓝色是子串）

![](https://img2024.cnblogs.com/blog/3397709/202410/3397709-20241015165257302-2028178304.png)

那么如下这种方案显然是一样的：

![](https://img2024.cnblogs.com/blog/3397709/202410/3397709-20241015165758601-203055203.png)

所以该结论显然是正确的。

**结论二：极长的弱子串的子序列和子串一定开头在整个串的开头要么结尾是整个串的结尾。**

这个结论比较显然，如图：

![](https://img2024.cnblogs.com/blog/3397709/202410/3397709-20241015171550573-34523219.png)

那么往左延伸时显然子串和子序列每个位置的字符都是相同的，所以一定可以延伸到两端。

对于前缀的一段，那么最长弱子串就是最后面的从后往前第一个相同的两个字符中靠前的那个字符的位置加上一。后缀同理。

跟据鸽巢原理，最多在第 $k+1$ 一个位置就会出现两个相同的字符。于是暴力枚举不同的位数，组合计算即可。

至于如何计算，可以容斥。用最长弱子串长度 $\le w$ 的串的数量减去长度 $\le w-1$ 的串的数量。

剩下的直接分类讨论前面第一次相等的位置的前缀与后面第一次相等的位置的后缀是否重叠，直接计算即可。

[code](https://codeforces.com/contest/135/submission/283866262)

## ZerOne

![](https://img2024.cnblogs.com/blog/3397709/202410/3397709-20241017143202154-620870728.png)

$$1\le n\le 100$$

考虑每次操作是交换两个子串，不难发现，每次交换完所有 ```1``` 所在的位置的编号和是不变的。而所有 ```1``` 所在位置的编号和与原串相等的串可以证明一定是可以构造出来的。所以本题等价于计数位置的编号和与原串相等且 ```1``` 的数量相等的串的个数。

考虑 dp。设 $f_{i,j,k}$ 表示前 $i$ 个位置，填了 $j$ 个 ```1```，位置编号和为 $k$ 的序列的个数。转移时分类讨论这一位填不填即可。

总时间复杂度 $\operatorname{O}(n^4)$。

[code](https://www.luogu.com.cn/paste/8w7whgju)

## [[JOI Open 2016] 销售基因链](https://www.luogu.com.cn/problem/P9196)

好题！可惜做的时候一直在想 hash 做法还没想出来......

首先考虑没有后缀的情况。那么可以直接放在 trie 上查子树内字符串出现个数，dfs 预处理一遍就好。

考虑现在加入后缀。那么我们可以对后缀也建立一棵 trie，那么问题转化为同时出现在两棵 trie 的两个子树内的字符串个数。

考虑求出 trie 的 dfn 序，那么现在就相当于转化成了同时在两个区间内出现的字符串个数。设一个字符串 $s$ 在第一个 trie 上出现的位置是 $i$，在第二个 trie 上出现的位置是 $j$。那么我们可以将其设为点 $(i,j)$。那么询问就可以转化为一个矩阵内点的数量，离线二维数点即可。

[code](https://www.luogu.com.cn/paste/sieoktrm)

## (ox) Alternative

![](https://img2024.cnblogs.com/blog/3397709/202502/3397709-20250212161638070-155567738.png)

$$1\le A\le 10^5, 1\le B\le 10^5, 1\le C\le 10^5, 1\le D\le 10^5, 数据组数\ T \ 不超过\ 10^5$$

一道很好的格路计数题。

首先我们可以注意到 ```o``` 的存在其实没有很大的意义，只要在最后将答案乘上 $\binom{A+B+C+D}{C}$ 即可。

接着考虑先找一些性质将问题简化一下。不难发现当 $A\neq B$ 时，如果 $D\neq 0$，答案一定为 $0$。$A=B=D=0$ 且 $C\neq 0$ 时答案为 $1$，那么接下来只要考虑 $A=B$ 的情况，于是现在把右括号的数量也视为 $A$。

考虑如果已经确定了 $A$ 个左括号和 $B$ 个右括号的排列情况，要将若干个 ```x``` 插入到序列中的方案数如何计数。注意到 ```x``` 插入的位置其前缀的左括号一定比右括号多至少一个，后缀的右括号一定比左括号多至少一个，那么以下这些黑线在的位置就是不合法的：

![](https://img2024.cnblogs.com/blog/3397709/202502/3397709-20250212162709933-1424310319.png)

注意到这些黑线将整个括号序列分割成了若干个合法的括号匹配，假设一共分成了 $k$ 个括号段，那么插入的方案数就是 $\binom{2A-k}{D}$。

那么就可以枚举一共分成了多少个括号段，然后计算方案。**假设当前分成了 $i$ 个括号段**，考虑该如何计算方案数。

首先先将这个问题稍微变下形，如图：

![](https://img2024.cnblogs.com/blog/3397709/202502/3397709-20250212172434462-1016063418.png)

不难证明，这三种形式是等价的。

将一个左括号视为在一个大小为 $A\times A$ 的矩阵上向右走一步，右括号为向上走一步。那么原问题就可以变为钦定了先向右走 $i$ 步，然后走到点 $(A,A)$ 且不**越过**直线 $y=x$ 的方案数，如图：

![](https://img2024.cnblogs.com/blog/3397709/202502/3397709-20250213073549777-81422198.png)

答案就是从 $(i,0)$ 走到 $(A,A)$ 的方案数。

考虑与从 $(0,0)$ 开始走一样操作。对于一条越过了 $y=x$ 这条直线的路径，可以在其第二次**到达**直线 $y=x$ 时将其剩下的部分以 $y=x$ 这条直线为中心翻折，比如下图绿色路径翻折成了紫色的路径：

![](https://img2024.cnblogs.com/blog/3397709/202502/3397709-20250213074232951-665177051.png)

一条合法的路径最后一定会经过点 $(A, A-1)$，所以说一条不合法的路径一定会经过点 $(A-1, A)$，所以说用 $(i,0)$ 到 $(A,A)$ 的方案数减去 $(i,0)$ 到 $(A-1,A)$ 的路径数即可，所以方案数如下：

$$\binom{2A-i}{A}-\binom{2A-i-1}{A}$$

那么答案式子为：

$$\binom{2A+C+D}{C}\sum_{i=1}^{A}\binom{2A-1-i}{D}\times (\binom{2A-i}{A}-\binom{2A-i-1}{A})$$

对该式子进行化简：

$$原式=\binom{2A+C+D}{C}\sum_{i=1}^{A}(\binom{2A-i}{A}\binom{2A-1-i}{D}-\binom{2A-i-1}{A}\binom{2A-1-i}{D})$$

$$=\binom{2A+C+D}{C}(\sum_{i=1}^{A}\binom{2A-i}{A}\binom{2A-i}{D}-\sum_{i=1}^{A}\binom{2A-i-1}{A}\binom{2A-i}{D})$$

考虑将枚举 $i$ 换为枚举 $A-i$

## [[AGC038E] Gachapon](https://www.luogu.com.cn/problem/AT_agc038_e)

一道很好的题，感觉和 [重返现世](https://www.luogu.com.cn/problem/P4707) 有点像，但推式子更为困难。

首先看到每个题目要求每个 $i$ 都出现了至少 $B_i$ 次，不难发现这是要求对于每个位置 $i$ 出现了 $B_i$ 次的期望随机次数的最大值，可以考虑使用 ```min-max``` 容斥：

$$\operatorname{E}(\max(S))=\sum_{T\subseteq S,T\neq \emptyset} \operatorname{E}(\min(T))\times (-1)^{|T|+1}$$

那么问题就变为了对于一个集合 $T$，期望操作多少次使得其中某个数出现次数大于等于 $B_i$。

首先如果一次操作选择的数在集合 $T$ 之外那么这次操作是没有意义的。设 $s=\sum_{i=1}^{n} a_i$ （下文的 $s$ 都是这个含义），不难计算出选择的数在集合内的期望操作次数：

$$P=\frac{s}{\sum_{i\in T}a_i}$$

那么现在只需考虑每次操作都选入了集合内的情况，最后乘上 $P$ 即可（若有 $k$ 次选在了集合里那么期望就是 $k\times P$）。

考虑需要多少次选择才能满足条件。可以通过如下式子进行转化：

$$\sum_i i\times \operatorname{P}(x=i)=\sum_{i}P(x\geq i)$$

于是现在只要考虑每次操作完都不满足的概率之和即可，也就是说要计算操作出一个数组 $c$ 满足 $\forall i\in[1,n],c_i<B_i$ 且 $\sum\limits_{i=1}^{n}c_i=k$ 的概率。这个东西很好计算，公式如下：

$$\prod_{i\in T}(\frac{s}{\sum_{i\in T}a_i})^{c_i}\times \frac{k!}{c_1!c_2!\cdots c_n!}$$

设 $F(T)=\sum\limits_{i\in T}a_i$，把原式变换一下形式得到：

$$原式=k!\prod_{i\in T}\frac{s^{c_i}}{F(T)^{c_i}c_i!}$$

现在已经计算出了如果每次都选入集合的期望次数，乘上 $P$ 可得到 $T$ 内存在位置满足其出现了至少 $B_i$ 次的期望操作次数（其中 $G(T)=\sum_{i\in T}(B_i-1)$）：

$$\sum_{k=0}^{G(T)}P\times k!\prod_{i\in T}\frac{s^{c_i}}{F(T)^{c_i} c_i!}$$

那么最后答案的式子就是：

$$ans=\sum_{T\subseteq S,T\neq \emptyset}(-1)^{|T|+1}\times (\sum_{k=0}^{G(T)}P\times k!\times F(T)^{-k}\prod_{i\in T,c_1+c_2+\cdots+c_n=k}\frac{s^{c_i}}{c_i!})$$

考虑我们需要得到的信息：

1. 容斥系数

这个东西很好处理，在后续 dp 转移时每次选择一个数就取反符号即可（详见 dp 转移式）。

2. $F(T)=\sum_{i\in T}a_i$

也就是说我们需要记录集合中出现的数的 $a$ 之和。

3. $\sum\limits_{i=1}^{n}c_i=k$

也就是说要记录选择了的序列的和。

剩余的贡献可以在 dp 中计算。

于是可以开始 dp 了。设 $f_{i,j,k}$ 表示前 $i$ 个数，我选择的这些数所选择的 $c$ 的和为 $j$，我选择的数的 $a$ 的和为 $k$，有转移方程：

$$f_{i,j,k}=f_{i-1,j,k}-\sum_{l=0}^{\min(B_i,j)}f_{i-1,j-l,k-a_i}\times \frac{(a_i)^l}{l!}$$

注意一下边界条件 $f_{0,0,0}=-1$ 即可。

[code](https://atcoder.jp/contests/agc038/submissions/62914929)

## [[AGC036D] Negative Cycle](https://www.luogu.com.cn/problem/AT_agc036_d)

神仙题。

发现这个东西在图上非常不好处理，考虑转化一下。

注意到题目的限制是不存在负环，于是很自然的能想到 SPFA。对于一张图，若其没有负环，则说明其差分约束有解，于是转化成了一个序列问题。

假设我们现在确定了最优的删边策略下差分约束的解为 $a_1,a_2,\cdots,a_n$。由于初始的 $(i,i+1,0)$ 的边无法去掉，所以一定有 $\forall i\in [2,n]\ a_i\geq a_{i-1}$，考虑其差分数组 $b$，那么有 $\forall i\in [1,n]\ b_i\geq 0$。

那么对于一对数 $(i,j)$ 满足 $i<j$，那么考虑其两条边能选择的情况的性质。

1. 边 $(i,j,-1)$ 可选择

那么有 $a_i-a_j\geq 1$，即 $\sum\limits_{k=i}^{j-1}b_k=0 \geq 1$。
也就是说如果 $\sum\limits_{k=i}^{j-1}b_k=0$ 就需要花费代价删除这条边。

2. 边 $(j,i,1)$ 可选择

那么有 $a_i-a_j\leq 1$，即 $\sum\limits_{k=i}^{j-1}\leq 1$。

也就是说如果 $\sum\limits_{k=i}^{j-1}b_k\geq 2$ 就需要花费代价删除这条边。

观察需要删去每条边的限制，不难发现对于差分数组的每一个 $b_i$，一定有 $b_i\le 1$，因为这样相较于 $b_i\geq 2$ 可以多满足 $(i+1,i)$ 这个限制且不会影响别的限制，于是现在就是要确定一个长度为 $n$ 的 ```01``` 序列 $b$。

设 $f_{i,j}$ 表示 $b_i=1$，且上一个为 $1$ 的位置为 $j$，于是有转移：

$$f_{i,j}=\max\limits_{k=0}^{j-1}f_{j,k}+Val(i,j,k)$$

其中 $Val(i,j,k)$ 是这一段产生的代价，分类讨论跨过的 $1$ 个数不同的区间，有二维前缀和维护一下即可。

[code](https://atcoder.jp/contests/agc036/submissions/62932045)

## [ソリティア](https://www.luogu.com.cn/problem/AT_joisc2016_c)

先分析一下怎样的矩阵可以填满。

首先四个角的位置显然不可能满足两条条件中的任何一条，所以这四个角必须已经填满。

对于第一行和第三行的位置，其不能满足第一种条件，所以只能通过条件二填满。那么就不能存在一个长度大于等于 $2$ 的连续段都是空的。

接下来考虑计数。可以考虑对每个位置分配一个数，代表其是第几个被填满的，类似于 [AT_dp_t](https://www.luogu.com.cn/problem/AT_dp_t)。

设 $f_{i,j,0/1}$ 表示第 $i$ 列，中间位置是第 $j$ 个被填的，填的方式是上下都满了/左右都满了。

转移时分类讨论一下当前位置的填法与上一个位置的填发即可。

1. **当前位置通过操作 1 填**。

前一列的填法可以是任意一种，且编号不重要，那么在这一列的第一行和第三行中对于没有填的位置选择一个比当前位置的编号小的即可。

2. **当前位置通过操作 2 填**

那么前一列一定要先填满，所以前一列的编号要小于这一列且填法一定是第一种，而这一列的第一行和第三行的编号大小关系不重要，乘上方案数即可。

两种情况都是 $\operatorname{O}(n)$ 的，但是可以用前缀和优化。总时间复杂度 $\operatorname{O}(n^2)$。

[code](https://atcoder.jp/contests/joisc2016/submissions/62931581)

正在渲染内容...