四月份训练手记

4.1 - 1 - Problem - H - Codeforces

思路

这道题主要是考察线段树的应用

不难发现，对于某一个字符串（不做修改），我们可以通过 DP 的方法来得到答案，只需要维护在某个点之前：

• 以 $1$ 结尾的答案总贡献和子串数量
• 以 $0$ 结尾的答案总贡献和字串数量

至于转移方法，我们只需要在新加入一个不同字符的时候更新贡献与子序列数量即可

那为了支持修改，我们需要使用线段树来维护以上信息，但线段树维护的是区间，而不是前缀

所以我们需要对子串的开头和结尾都进行分类

并且在合并的时候，考虑所有情况的贡献，减去那些中间字符相同（比如 $01$ 和 $10$ ）的两个串合并后的贡献是两个串的贡献相加再 $-1$

收获 & 反思

线段树的又一应用方法

对于区间上贡献具有一定的 **“可加性” 或者 “分类可加性”**，的时候，就要考虑使用线段树来维护

对于 “线段树是在维护幺半群上的信息” 这句话的理解又加深了一点

4.1 - 2 - Problem - I - Codeforces

思路

我们先考虑，如果是朴素的贪心，怎么来解决问题：

• 首先对于每一个有序对 $(x,y)$ 都可以用贪心统计答案：先遇到哪个字符，我就先加入序列
• 不难证明，这样找到的序列一定是最长的

思考一下，这样的贪心解法对于我们的解答有什么启发呢？

进一步地说，在这种贪心策略下，某一个位置的字符，在什么情况下才会被 “收录” 到某一个有序对 $(x,y)$ 的答案当中，进而对最终答案产生贡献呢？

考虑到我们贪心的过程，答案也是显然的：

• 在某一轮贪心中，只有这个字符与前一个相同字符之间，有一个目标字符（有序对中的另一个字符），这个字符才会被 “收录”
• 如果没有前一个字符（首次出现）则一定会被收录

那我们的贡献统计就变得简单起来了，对于每一个位置：

• 如果是第一次出现，一定会产生贡献， $cnt=m-1$ 之所以要减一是因为它不能和自己构成有序对（题目限制）
• 否则，我们找它和前一个相同字符之间，统计其中不同字符的个数，就是它的贡献值

问题又转化为了：如何统计区间上的不同字符个数

对于普适的做法，我们可以使用主席树（可持久化权值线段树）来统计区间上不同数值的个数

但这道题不需要那么复杂，因为我们要求的区间具有 右节点严格非降的后缀区间 性质，在这个条件下，就可以记录每个字符最后一次出现的位置，并且标记为 $1$ ，然后树状数组维护区间和与单点修改就可以了

收获 & 反思

思路相当值得学习！

这道题的几个关键点：

• 用贪心简化问题，便于考虑
• 用贡献法转化问题，使得枚举量变为 $O(n)$
• 利用待统计区间的特殊性质，用树状数组完成区间字符种数的统计

4.2 - 1 - Problem - G2 - Codeforces

超级神秘好题

思路

我们考虑对于一组数 $(p_i,p_j)$ ，它们满足要求的条件是 $ij\mid p_i{p}_j$

不难注意到，$p_i$ 和 $i$ 总是同时出现的，所以不妨预处理一下，令 $x_i=\frac{i}{gcd(i,p_i)}$ ，$y_i=\frac{p_i}{gcd(i,p_i)}$ ，其中有 $x_i\perp y_i$

于是题目要的条件就变成了 $x_i{x}_j\mid y_i{y}_j$ 由于 $x_i\perp y_i$ 并且 $x_j\perp y_j$ 于是条件进一步变为：

• $x_i\mid y_j$ 并且 $x_j\mid y_i$

一个很自然的想法就是，我们枚举所有可能的 $x$ ，然后枚举是 $x$ 的倍数的 $y$ 的值，对于这些 $y$ 来检查，然后统计答案

但是这样子做有一个问题：我们前两层枚举的时间复杂度是 $O(n\log n)$ 的，但是有可能对于某一个很小的 $x$ ，有相当多的点，这个时候检查的时间复杂度就会超出限制

如何才能保证时间复杂度严格低于限制呢？

我们考虑上一个方案的缺点是什么，就是对于一个体量很大的 $x$ （也就是有很多个 $i$ 都满足 $x_i=x$），我们在枚举可能的 $j$ 的时候，需要对每一个 $i$ 都去判断，效率是很低的

考虑使用预处理来提高效率

我们的检查是在做什么？是在检查每一个可能的 $j$ ，有几个 $i$ 能满足 $x_j\mid y_i$ ，也就是说其中有几个 $y_i$ 的因数包括了 $x_j$ ，那我们就可以提前统计出每一个因数出现的次数，然后每次直接统计贡献

为什么这样时间复杂度是正确的？

首先每个数只会在初始阶段被枚举一次，对应的就是二层的枚举量严格小于 $n\log n$，同时考虑枚举因子的开销，也是每一个 $y_i$ 只会被枚举一次，所以枚举因子的开销也严格小于 $n\log n$ ，证明完毕

收获 & 反思

这道题做法难度不高，但是其中涉及到了较为复杂的时间复杂度优化想法与时间复杂度的正确性证明

解决的方法有很多，但是其中相当一部分可以被精心构造的数据卡到 $TLE$ ，所以需要我们牢固掌握时间复杂度的分析和优化手段，设计出严格时间复杂度的 $Solution$

4.3 - 1 - Problem - E3 - Codeforces

这次会用倍增了

思路

看到这道题就想到了应该可以倍增，因为：

• $n$ 的范围巨大，显然无法直接计算
• 题目中对于转移的限制较低，可能可以转化为统一计算的方案

但是倍增的对象还需要精心选择：

• 如果选择每个木屋的方案数，在统计的时候并不方便，而且时间会超出限制
• 如果选择第 $i$ 天的方案数，则没有有效的转化手段

这个时候应该思考到：什么东西状态量少，可以倍增（可以转移），并且可以导出最终答案呢？

不难发现，如果抛开限制，我们既然每天都要前往湖心岛，那我们就可以把这个时候当作一个节点，从湖心岛出发之后再回来的方案数是可以计算的，还支持倍增

但是考虑到题目中的条件，那就要求我们前一次到达湖心岛与后一次离开必然有一次走短路，所以就可以分类维护出发与回来走的路的种类，然后进行条件转移

最后的答案就是考虑从 $1$ 号房子出发，有多少种方案到达湖心岛，最后一天又有多少种方法可以走到其他房子

收获 & 反思

合理设计倍增的对象，就可以变魔法！

4.3 - 2 - Problem - B2 - Codeforces

思路

因为 $a+b\mid bgcd(a,b)$ ，两边同除 $gcd(a,b)$ 后即为 $a^{\prime }+b^{\prime }\mid b^{\prime }gcd(a,b)$，其中 $a^{\prime }\perp b^{\prime }$

所以也有 $b^{\prime }\perp a^{\prime }+b^{\prime }$ ，所以就有 $a^{\prime }+b^{\prime }\mid gcd(a,b)$

于是我们就可以枚举互素的 $a^{\prime },b^{\prime }$，，再枚举 $gcd(a,b)=k(a^{\prime }+b^{\prime })$ 因为要满足：

$$\{\begin{array}{rl}& a=a^{\prime }\times gcd(a,b)=k{a}^{\prime }(a^{\prime }+b^{\prime })\le n\\ & b=b^{\prime }\times gcd(a,b)=k{b}^{\prime }(a^{\prime }+b^{\prime })\le m\end{array}$$

所以合法的 $k$ 的数目就是：

$$min\{\lfloor \frac{n}{a^{\prime }(a^{\prime }+b^{\prime })}\rfloor ,\lfloor \frac{m}{b^{\prime }(a^{\prime }+b^{\prime })}\rfloor \}$$

不难发现这里的 $a,b$ 均大于 $a^{\prime 2},b^{\prime 2}$ ，所以我们只需要在 $\sqrt{n},\sqrt{m}$ 的范围内分别枚举即可，时间复杂度 $O(\sqrt{nm})$

收获 & 反思

善于运用互素结论，可以更好的分析题目

4.4 - 1 - Problem - D - Codeforces

思路

赛时脑子抽了

其实就是一个背包 $dp$，很简单地考虑 $dp[i][j]$ 是只考虑前 $i$ 种字母，其中有 $j$ 个奇数位已经被占据的方案数

记每个字母的数量是 $cnt[i]$ ，字母总数是 $sum$ ，$cnt[i]$ 的前缀和是 $pref[i]$

那转移方程就是：

$$dp[i][j]=\{\begin{array}{rl}& dp[i-1][j]\times (\genfrac{}{}{0ex}{}{\lceil \frac{sum}{2}\rceil -(pref[i]-j)+cnt[i]}{cnt[i]})\\ & dp[i-1][j-cnt[i]]\times (\genfrac{}{}{0ex}{}{\lfloor \frac{sum}{2}\rfloor -j+cnt[i]}{cnt[i]})\end{array}$$

需要注意其中一些项的转移条件

第二种方法就是，先用数学方法推导发现奇偶性排列的方案与最终字符串排列的方案无关，故可以直接先求出方案数，最后再计算组合数，本质上是一样的

收获 & 反思

需要针对题目选择不同的解决方案

4.4 - 2 - Problem - D - Codeforces

思路

不难注意到，对于最大值我们是一定要选取的，证明如下：

• 如果不选最大值，那么至少会带来一点减益
• 此时去选最大值，最小值一定非降，$siz$ 至多减一，使用一定不会更劣

那么我们就可以考虑枚举我们要取到的最小值，我们可以把每一个数按照大小先排序，然后从大到小加入

我们可以用并查集来维护答案：

• 对于每一个连成一段的区间，我们最优就是每隔一个去选取，并且区间长度为奇数的时候，要从第一个开始选取
• 我们可以记录在这些区间里最大值出现了几次（偶数长度区间就取较大值）然后判断需不需要牺牲一个位置来取最大值
• 每一轮维护之后，答案就是 $max+min+siz$ 这里的 $siz$ 是各个区间统计的可以取到的最多格子数量，并且经过了判断是否需要减一（牺牲一个格子保证最大值）

收获 & 反思

维护最大值能不能被取到的时候，可以维护区间数量而不只是 “能或不能”，这样更方便维护

对于这样取最值的题目，充分考虑性质之后，可以使用动态方法维护 + 枚举部分条件的方法求解

4.4 - 3 - Problem - H - Codeforces

思路

这是经典的 2-SAT 问题，每个元素选与不选就是每个 $a_i$ 的值是 $1$ 还是 $-1$

然后，对应的，2-SAT 问题的子句就是对应的 B 矩阵中的每一个纵列，任何两个元素不能同时为 $-1$

收获 & 反思

学习了 2-SAT

使用 Tarjan-SCC 求解

4.5 - 1 - Problem - E - Codeforces

思路

很简单，一眼就是求 $kth$ 祖先的题目

首先判断，对于两个点，如果他们之间的距离是奇数，一定无解

其次，如果两个点重合，则任意一个点都可行

再次就是，如果两个点深度相同，那么他们简单路径的中点（也就是 $LCA$） 的子树外的所有节点也都可以满足条件

其他的点，也就是有解并且到 $LCA$ 的距离不相等，就只有其简单路径的中点的子树上，除去包含两点的子树后剩下的节点

收获 & 反思

倍增求祖先的简单运用，没什么好说的

4.5 - 2 - Problem - E - Codeforces

思路

赛时没做出来纯糖哇

这是一个 “合理拆贡献” 的好例题，如果不能合理拆分贡献，就会使得这道题很难做（当然你会 NTT 大力出奇迹当我没说）

首先明确题意：对于所有可能的排列，求出所有区间 $mex$ 值的总和

一个很自然的想法是，我们考虑对于每个区间，枚举其可能的 $mex$ 值并且统计对应的排列，但是这是 $O(n^3)$ 的，时间接受不了

所有我们需要改变求解思路，考虑贡献法

这里有一个很巧妙的转化，我们把所有区间的 $mex$ 值总和转化为：

$$\sum _{i=0}^n\mathrm{包}\mathrm{含}\mathrm{所}\mathrm{有}[0,i]\mathrm{中}\mathrm{的}\mathrm{数}\mathrm{的}\mathrm{集}\mathrm{合}\mathrm{数}\mathrm{量}$$

为什么这样是对的呢？不难发现，$mex$ 值为 $k$ 的区间，会对于 $i=[0,k-1]$ 均成立，也就是产生 $k$ 次贡献，所以这样计算是等价的

这是贡献法中的一种 “差分思想”，适用于条件和贡献具有一定单调性的情形

那我们该怎么统计这类集合呢？又该怎么求解呢？

首先我们注意到，如果要满足前 $k$ 个条件，必须要有前 $k$ 个数，并且其中一些数已经被固定了（在数组中给出）

所以我们在考虑区间可行的最大 $mex$ 值的时候，需要注意有没有在数组中的，小于 $k$ 值的数不被包含在区间里，如果有的话，那么我们的 $mex$ 值无论如何也不能超过这个数

换而言之，如果出现在数组中小于 $k$ 的所有数都被包含在了这个区间里，那么只要有足够多的空位，他是可以满足任何 $mex\le k$ 的条件的

所以，我们就可以统计出 $cnt[i][j]$ ，表示数组中小于 $i$ 的数（$i$ 在此取最大值）都在区间里，并且有 $j$ 个空位的区间数量

然后对这个数组进行第一维上的后缀求和，新数组 $cnt[i][j]$ 的意义就是数组中小于 $i$ 的数（$i$ 在此不一定是最大值，只是满足）都在区间里，并且有 $j$ 个空位的区间数量

然后对于 $cnt[i][j]$ ，如果空位数 $j$ 大于等于在 $i$ 前未出现在数组中的数的数量 $need[i]$，就可以排列组合出满足条件的区间，满足条件的区间数就是在 $j$ 个位置中选出 $need[i]$ 个，然后把这 $need[i]$ 个数与剩余的空位分别求排列数相乘，也就是：

$$(\genfrac{}{}{0ex}{}{j}{need[i]})\times need[i]!\times (need[n]-need[i])!$$

就这样就做完了

4.6 - 1 - Problem - 1997E - Codeforces

思路

不妨把条件做一下转化：

• 对于第 $i$ 只怪物，如果前面发生过至少 $k\times a_i$ 场战斗，那么怪物会逃跑，否则将发生战斗

那我们不难发现，对于任意时刻，$k$ 大的时候，此时的战斗力一定不会更强，这一点可以使用数学归纳法证明

那么我们只需要计算对于某个位置，$ans [i] $ 记录当 $k$ 至少为多少的时候，战斗无法避免

也就是说，对于 $k$ ，在这个位置之前发生的战斗数量就是此前 $ans[i]\le k$ 的 $i$ 的数量

对于每一个位置，我们可以用树状数组维护并实现查询 $ans[i]\le k$ 的 $i$ 的数量，从而二分求取此处的 $ans[i]$

那么就做完了

收获 & 反思

很巧妙的转化思路，一些可能的思考启发是：

• 对于此类问题，考虑 “什么东西具有单调性”，在此处是每个点处的战斗力与 $k$ 的关系，进而是每个怪物是否会发生战斗与 $k$ 的关系
• 然后就是树状数组的应用，应该考虑到答案可以以什么形式来存储并维护

4.7 - 1 - Problem - D - Codeforces

思路

很巧妙的思路

对于 $n=1$ 特判

对于剩余情形：

• 若 $n$ 为偶数：
  • 我们令前 $\frac{n}{2}$ 个数与后 $\frac n2-1 $ 个数为'a' ，这样保证了所有仅由 'a' 组成的子串出现的次数均为奇数（前后出现次数相差一）
  • 然后令中间为其他任意字母即可
• 若 $n$ 为偶数
  • 与奇数处理方法类似，只不过中间两个字母为任意两个不同的其他字母

构造完毕

收获 & 反思

题目不难，但是思路很优美

考虑构造一个东西是奇数，就可考虑构造两个部分，使得这两个部分一个是奇数，一个是偶数（特别地，可以使得两个部分相差一）即可

4.7 - 2 - Problem - G - Codeforces

思路

很自然的想法是，我们无法确定什么时候可以出发，所以不确定通话在出发后多久开始，所以不妨将整个过程逆转，考虑从活动地点到家里的最短耗时，这样通话区间与出发时间的关系就是确定的了

我们考虑一个最快的流程应该是怎样的：

• 在通话开始前就可以到家
• 在通话开始前下车，在通话结束前步行到家
• 在通话开始前下车，在通话结束后步行或坐车到家

那我们就可以考虑分几个部分来解决问题：

• 先考虑在 $t_2$ 之前，坐车能到哪些位置，此时如果能直接到家则得到答案
• 然后新建一个图作为通话时的情形，建上所有步行边，同时从 $n$ 点向上述坐车能到达的点连一条有向边，长度即为花费的时间
• 再求一轮单源最短路，看看能不能步行到家
• 如果不能，我们就枚举打完电话后上车的位置，在打电话前花费的时间就是 $max(dis,t_1)$ ，打电话后花费的时间就是坐车到家的最短开销

做完了

启发

对每个过程都做贪心处理，用有限的枚举充分考虑所有情况

4.7 - 3 - Problem - H - Codeforces

思路

用前缀和转化

一个是原矩阵的前缀和，一个是给所有数都乘上顺序权值的前缀和，还有一个给所有数按行乘上权值的前缀和

用这三个前缀和合理组合就可以计算出答案，没什么难的

收获 & 反思

没什么好说的（才不会告诉你 for 循环写锅了一次）

4.8 - 1 - Problem - 765D - Codeforces

思路

不难发现，如果有 $h(g(x))=f(x)$ ，那么令 $x=h(x)$ 就有 $h(x)=f(h(x))$ ，也就是说，$h(x)$ 的取值只能是那些 $f(x)=x$ 的 $x$ 值

然后考虑 $g(h(x))=x$ ，也就是说对于每一个 $h(x)$ 都要有对应的一个 $g$ 值为 $x$

那我们从必要条件入手，对于每一个 $f(x)=x$ 的值，我们建立一个其在 $h(x)$ 中的映射，并且由于第二个条件，对应编号的 $g(h(x))$ 必须等于 $x$ ，此时第二个条件已经完全满足

那就考虑第一个条件，除此之外，每一个 $f(x)$ 都需要被表示，那么就遍历检查：

• 对应的位置如果还没有确定映射关系：
  • 有没有可供映射的 $h(x)$，如果没有就 Fail
• 如果已经有映射关系：
  • 映射的值是否正确，如果不正确就 Fail

如果都满足，那么就是一组合法的解

收获 & 反思

不错的一道思维题，有点绕绕的，最重要的是抓住 “$h(x)$ 的取值只能是那些 $f(x)=x$ 的 $x$ 值” 这个突破口

4.8 - 2 - Problem - 2075F - Codeforces

思路

首先转化题意，即求最大的一个子序列，使得左端点唯一严格最小，右端点唯一严格最大

然后我们将数组转化为二维点 $(i,v[i])$ 手玩一下，不难发现一个贪心策略：如果有 $i<j,v[i]<v[j]$ ，那么 $i$ 做为左端点在任何时刻都是优于 $j$ 的，同理有右端点的类似的贪心策略

也就是说，对于这样的 $i$ 和 $j$ ，$j$ 是一定不会作为左端点的，这是一个类似于单调栈的结构，于是我们可以筛选出所有可能作为左端点（右端点）的点

然后我们考虑一个点可以在取那些左右端点组合的时候产生贡献：

• 由于所有可能作为左端点（右端点）的点是单调的，所以这个贡献区间一定是形如 $[l1,r1],[l2,r2]$ 这样的连续区间
• 那我们统计贡献就可以转化为将其中一维化为坐标轴，对另一维扫描线计数，线段树维护最值即可

做完了，思路，，，好神奇，好优雅

收获 & 反思

很优美的思路，我可能还没办法总结出什么，但是有以下几点：

• 考虑可能的贪心，他可能带来让问题变得可解的关键性质
• 善于应用单调栈
• 善于考虑贡献的转化，能否用贡献求解
• 对于形如在两个维度上的连续区间的限制，可以转移到 “对一个矩阵区域有贡献” 上，进而可以使用扫描线处理（以其中一个维度作为坐标轴）

4.9 - 1 - Problem - 1666E - Codeforces

思路

看到求可行的最值，考虑二分

首先是二分路段的最大差值 $\mathrm{\Delta }$，然后考虑能不能 check ，怎么 check ？

显然我们可以枚举这个差值下，路段长度的上下界 $[l,l+\mathrm{\Delta }]$

然后对于这个上下界，我们显然是可以判断出可行性，并且若可行，我们可以逆过来求出一组合法的解的

同时不难发现，如果不可行，必然是因为太长 / 太短，这是什么？这是宝贵的单调性啊！

也就是说，我们可以通过二分 $[l,l+\mathrm{\Delta }]$ ，来完成对 $\mathrm{\Delta }$ 的 check

就做完了

收获 & 反思

"Stop learning useless algorithms, go and solve some problems, learn how to use binary search."

4.10 - 1 - Problem - 1458C - Codeforces

思路

这个考虑非常巧妙！！！

我们将每一个矩阵中的元素记作一个三元组 $(i,j,va{l}_{i,j})$ ，这样就完全表示了矩阵中的每一个元素

那么就不难发现，每一个元素在对应操作下的 “去向”：

• $L/R$ ：$(i,j\mp 1,va{l}_{i,j})$
• $U/D$：$(i\mp 1,j,va{l}_{i,j})$
• $I$ ： $(i,va{l}_{i,j},j)$
• $C$ ： $(va{l}_{i,j},j,i)$

于是我们记录这些变化的复合，最后对于每一个元素应用变化，就可以得到目标矩阵

收获 & 反思

如果发现对于一个矩阵上的元素很难维护 “每一个位置上的数”，不妨转而维护 “原来的数变成啥？都去哪了？”

这对于一些有固定变化方式的运算有奇效

值得好好学习的一道题！

4.11 - 1 - Problem - B3 - Codeforces

思路

关注到一个很重要的点：每一列有且只有一个房子，并且距离是在 $[0,n]$ 中任取

那么我们从第一列开始考虑，把第一个数放在 $(1,1)$，就有如果 $a_i<i$ 那么一定可以找到之前的某一列，和他直接匹配上，否则，就一定可以找到一个位置，和 $(1,1)$ 成功匹配

这样子我们就可以把之后的所有房子都成功匹配，但是问题来了，第一个房子怎么办？

很容易想到的是，如果数列中有某一个 $a_i=0$ ，那么把它放在第一个就可以让他和自己匹配

如果没有 $0$ 呢？也不难注意到，两个 $a_i$ 相同的话，把他放在第一和第二个，他们之间可以互相满足，也解决了第一个的问题

最后，如果没有 $0$ ，也没有重复，那就是一个 $[1,n]$ 的排列，这个时候我们去手玩一下，发现：

• 如果 $n\le 2$ 那么无解
• 否则，可以让 $1,2,3$ 分别位于 $(2,1),(3,2),(1,1)$ ，这样使得第一个可以合法匹配

到这里就做完了

收获 & 反思

需要注意条件的特殊性质，比如：

• 每一列有且仅有一个
• 根据 $a_i$ 的大小一定能找到解
• 构造特殊的开头使得第一个房子得以匹配

4.11 - 2 - Problem - D - Codeforces

思路

一个很自然的思路是，如果 $k$ 小于等于 $\lceil \frac{n}{2}\rceil$ 的话，我们可以直接把第一个摊位设为 $n-k+1$ ，第二个摊位设成 $1$ ，这样就一定满足条件

此外，如果 $k$ 大于这个数，那么我们可能整出的商品总数一定只能是 $n$ ，因为除此之外最大的就是把第一个设为 $2$ ，第二个设为 $1$ ，结果并不会比 $\lceil \frac{n}{2}\rceil$ 来得大

所以除了这两种情况就是无解

收获 & 反思

又是一个充分条件入手证明必要性的构造题

4.12 - 1 - Problem - E - Codeforces

思路

其实很简单：

• 不难注意到，其中的最大值一定同时作为（最后一个）前缀最大和（第一个）后缀最大出现
• 同时，第一个和最后一个也一定是前 / 后缀最大值
• 也就是说，不满足上面两个条件的，就一定是不合法的条件组

那我们考虑，其余情况都有合法的解吗？如果是，我们怎么统计解的总数呢？

我们首先明确，最大值左边显然不会有后缀最大值，同样的右边不会有前缀最大值

那就是把左右两边分开求解了，这种情况下，由于没有重复元素，所以无论怎么分配都是等价的

那我们只考虑其中一边，以前缀最大值为例：

• 既然已经确定了后一个前缀最大值在位置 $p_{i+1}$ （最开始的时候就是最大值的位置），那也就说明前面还有 $p_{i+1}-1$ 个数，再考虑前一个前缀最大值
• 因为前一个前缀最大值是往前首个前面没有任何数比他大的数，所以前面所有数中的最大值不能在他前面，也不能在他后面，所以他就是前面所有数中的最大值
• 那么还剩下 $p_{i+1}-2$ 个数可以被支配，且他们都比选出的数小，那方案数就是从中任选 $p_{i+1}-pi-1$ 个数随机排列放在前后两个前缀最大值中间
• 再往前也是一样的子问题形式，只需要将左右方案数都求出来，最后乘上最开始分配两边数的方案数即可

至此问题得解。

收获 & 反思

考虑把问题分解为子问题，不重复不遗漏，最简化问题建模，这是需要大量训练的

手动取模又出锅了调了快一个小时，我是傻逼