2023 NFLS 集训记录（补档）

· · 个人记录

标号 * 表示是不错的套路题，标号 & 表示是不错的思维题（），特别好的打两个。

Week 1

5.23

& A

题意：

有 n 份作业，分为两类，第 i 份作业可以在 [L_i,R_i] 这段区间内完成。

每天可以从两类作业中选择一类，并完成此类作业中未完成过的、当前可以完成的、截止日期最早的一份完成。

分别问最多、最少可以完成几份作业。1\le R_i,n\le 400。

场上卡了好长时间，以后要加训网络流！

不过其实是有 DP 做法的，我场上好像还否定过不能 DP（

对于最大值，两类作业可以放在一起考虑，根据题意贪心即可，最小值才是困难的。

首先是网络流做法，我的做法：

答案显然等于不做作业的天数。

对于两类点分别选择一些作业不做，这样如果一个日子在两类点中都有作业不做，那么这些日子是不能产生贡献的。

否则剩下的日子在做完要做的作业后都是可以产生贡献的，因此答案是剩下的天数减去要做的作业数。

假如有作业做不完，一定存在一种不劣的能做完方案，所以不需要考虑合法性。

这可以建三层图然后跑最小割做到 \mathcal O(n^{\frac{8}{3}})，配合线段树优化建图可以做到 \mathcal O(n^{\frac{5}{3}}\log n)。

题解做法更为形式化：

设选第一类点的天数集合为 S，注意到答案就是（两部分） S 和作业的最大匹配（之和）。

而最大匹配的最小值有点阴间，可以转化为最小点覆盖。

这样就可以 DP 了，记 f(x,y,z) 为考虑前 x 天，两类点中前一个不选的点是 y/z 的最小点覆盖数，这样可以转移。

具体见http://www.nfls.com.cn:10611/article/3918，复杂度 \mathcal O(n^3)。

启示：要尽可能形式化地转化问题 / 二分图的若干对象值相等，可以根据问题的 \min / \max 属性转化。

B

原题数据范围下为假题。

给定一个 n 个点 m 条边的无向图（可能有重边自环），边带权，权不超过 V。

一条路径的 XOR 和定义为其经过的所有边的权值的位异或和。路径可以经过重复边，重复经过的边其权值也会统计多次。

$n,m,Q$ 同阶，复杂度要求 $O(n\sqrt{n}\log^2V)$。

回滚莫队，维护可回退并查集以及线性基。

* C

有一个 n\times n 的矩阵，给定其内 m 个矩形。

对每个点定义颜色：假如有奇数个矩形覆盖了这个点那么它是黑色，否则它是白色。

现在给定 Q 次操作，每次反转一个单点的颜色。每次操作后建图求出最大匹配。

其中，在同一行或同一列中的不同色的点之间有边，可以匹配。

要求维护最大匹配只能用 Hall 定理，我们写出答案的形式：

ans=|L|-\max_{S\sube L}\{|S|-|N(S)|\}

注意到 N(S) 一定是若干行和若干列的形式，而且 N(S) 确定后最大化的 |S| 也是确定的。

我们枚举选行 R 和选列 C 的集合，有：

\max_{S\sube L}\{|S|-|N(S)|\}=\max_{R,C}\{|R||C|-F(R,C)-F(U,U)+F(\overline{R}, \overline{C})\}

其中 F(R,C) 表示 \sum_{x\in R,y\in C} [v_{x,y}=1]，这个东西可以被写作：

\max_{R,C}\{|R||C|-F(R,U)-F(U,C)\}

假如我们枚举完 R，那么 C 同时也是确定的：我们选择所有 |R|-F(U,c)\ge 0 的列即可。

代数地看，对于一列，其选择情况是单调的。同时假如我们确定一个 |R|，那么对应的 R 也是确定的。

考虑用线段树维护 |R| 的决策，这样一列的贡献对应在线段树上是一个区间加，行的贡献也是一个区间加。

修改的话，直接去掉原来的贡献换成新的即可。应用线段树维护之，复杂度 \mathcal O(n\log n)。

注意左部点是 0，不要搞反。此外 |R| 可以为 0，注意和 0 取 \max。写起来是真的答辩。

总结

rk 28/51，一塌糊涂。

客观地讲，今天 T1 反而是思维难度最大的题，T2 是假题，非常离谱。

不过也有一些主观原因，比如被 T1 卡了就摆烂了不去做后面的题，还是心态问题。

以后有空了得指定一个比赛常规计划，保证每个题至少 1h。今天的 1h 都在打暴力属于是。

南外每天一场模拟赛是真的阴间啊，订题时间很少，有些题甚至要放到周末订。

5.24

大便场。为啥 nfls 的模拟赛难度不按顺序排的，三个题难度还差不多？？？

** A

题意：http://www.nfls.com.cn:10611/up/NOI2021%E6%A8%A1%E6%8B%9F%E9%A2%98ASDFZ/day1_p1.pdf。

给定一棵以 1 为根的树。每次随机选择树上未被删去的一个点，将它和它的子树中所有点删去。

如果选到根，就把整棵树删去，并停止这一过程。

求 k 次内能把这棵树删空的概率，答案对 998244353 取模。

一个不错的套路题，但没见过这些套路，场上也没想出来。

这个题直接 DP 某个式子经尝试是不行的，要马上放弃掉。

正解依赖于一个转化：

考虑随机枚举一个排列 p，依次判断能不能删除 p_i，若不能删除（有一个祖先已经被善果）就忽略这个 p_i。

这样 删除次数 这个随机变量的分布和原题是一样的。

大致思路就是 \prod \dfrac{1}{n-\sum siz} 这种阴间东西不独立没法 DP，需要转成在所有数中取（类似于 PKUSC 猎人杀）。

但是重复删这里做不来，规整一下这个东西就是选排列的形式，答案是一样的。这个套路还是得记一记！

证明可以考虑假如 x 这个关键点的下一个关键点是 y 在原题中概率是 \dfrac{1}{m(m-siz_x)}，其中 m 是选 x 时的总大小。

而在转化过的题目中的概率为：（不在 m 中的数显然不用考虑）

\dfrac{\binom{m-1}{siz_x-1}(siz_x-1)!(m-siz_x-1)!}{m!}=\dfrac{1}{m(m-siz_x)}

这样可以导出一个 DP。

对于 x 的子树，我们算出这棵子树的排列中有 y 个点是关键点的概率。

但这个还没法转移，因为要加一个根进去，所以我们再记一维状态，表示：

对于 x 的子树，记这棵子树的排列的前 z 位中有 y 个点是关键点的概率。

这是二维树上背包，是 \mathcal O(n^4) 的，可以利用插值优化到 \mathcal O(n^3)。

大致原理就是一个复杂的计数过程中有一维是（多项式的）卷积形式时可以插值，因为多项式乘法是 \mathcal O(n^2)，插值等价于 \mathcal O(n)。

& B

题意：http://www.nfls.com.cn:10611/up/NOI2021%E6%A8%A1%E6%8B%9F%E9%A2%98ASDFZ/day1_p2.pdf。

给定一个长度为 n 的 01 串 S，可以进行两种操作：

  1. 将 S 中的最后一个字符删去，放入序列开头。
  2. 将 S 中的最后一个字符删去，放入第二个数前。

求使该串升序排列的最小操作次数，n\le 10^5。

贪心题。

我们把整个串看成一个环，然后维护一个指针表示 n 的位置，这样两种操作分别是：

首先是一种 \mathcal O(n\log^2 n) 做法，就是注意到我们最后一定是把所有 1 聚到一起，因此最终的状态只有 n 种。

枚举完状态后我们可以证明一定存在一个断点，左边的往左走，右边的往右走。

这样复杂度是 \mathcal O(n^3)，算答案的过程可以单次 \mathcal O(\log n)（猴汁说可以 \mathcal O(1)，未知真假），可以做到 \mathcal O(n^2\log n)。

然后这个断点是 \max(a,b) 的形式，而且 a,b 都是单调的，可以二分，做到 \mathcal O(n\log^2 n)，但是代码极其答辩，狗都不写。

此外有一种较为阳间的 \mathcal O(n) 做法，大致就是枚举完最终状态后上面的东西可以 \mathcal O(1) 构造。

具体地，我们判断掉全为 1 的情况后，首位一定是 0，那么我们将原序列的第 2\sim n 个位置（不含首位）看成一个环。

在序列结尾设置一个指针，于是操作变为：

我们枚举最终状态，假如所有 1 在 [l,r] 之中，设 [l,r] 中有 S 个 0。

设指针从 l-1 转一圈回到 l-1 的过程为一轮，那显然一轮最多只能（且一定能）带走一个 0 换成 1。

于是假如起始点 n=l-1 且 a_{l-1}=1（即第一轮开始前无法换数），那么总操作数一定是 (S+1)(n-1)+n-r，意义是：

我们考虑在第一轮开始前能不能换进来一个 1，使 S 减去 1。不难发现本题只剩下判断这个部分了。

假如 n\in [l,r]，那么进来的这个 1 必然来自首位，充要条件是 a_1=1 且 [l,n] 中有 0；否则充要条件是 a_1 或 (r,n] 中有 0。

C

问题转化后唯一的难点是求：

所有长为 n 的合法括号序列中有多少子序列 )(，n\le 10^7。

题解做法是：

http://www.nfls.com.cn:10611/up/NOI2021%E6%A8%A1%E6%8B%9F%E9%A2%98ASDFZ/day1_sol.pdf。

考虑两对匹配的括号之间的贡献，若它们相离则贡献为 1，否则即为包含，贡献为 0。

而相离的括号对组数可以从包含的对数中容斥出来。

而包含的对数可以枚举外面那个括号中包了 k 个括号，再把它插入到一个大的括号串中即可。

答案可以 \mathcal O(n) 计算得到。

同时它也是 OEIS A029760，有简单的递推式、通项式。

5.25

今天打得一般，主要还是被 T2 这个答辩题搞了。为啥 nfls 模拟赛全是答辩题？？？

A

给定一张仙人掌，和一个仙人掌上的节点 e，定义 dis_x 表示 e 到 x 的最短路经过的边数。

对于一个长度为 n 的排列 p，认为它是好的当且仅当对于仙人掌上的所有边 (u,v)，若 dis_u<dis_v，有 u 排在 v 前，否则有 u 排在 v 后，保证对于所有边有 dis_u\ne dis_v。

求所有好的排列的数量，对 998244353 取模。n\le 5000。

简单题，建出圆方树，在方点上区间 DP 即可。

B

(*3500) CF1439E。

首先把博弈模型建出来，整个游戏的 SG 函数就是每个点 2^{dep} 的异或和。

因此推一推可以知道答案就是当前 SG 函数中 1 的连续段数乘 2，假如根为 1 再减去 1。（也就是断点个数）

接下来最大的问题是如何处理这个东西。最常见的思路是建出虚树转化为暴力问题，但我没想到这个（

建虚树的过程需要支持比较两个点的 DFS 序和求 LCA，这两个操作都可以在 \mathcal O(\log V) 时间内完成。

总复杂度 \mathcal O(n\log n\log V)，假如使用分治建树可以做到 \mathcal O(n\log V)。

启示：问题中有很大的树，而且要考虑若干路径信息就考虑建虚树。

这和离散化类似，是一个找到最简信息后转化成小范围问题的思路。

&& C

(*3500) CF1444E。

阴不阴间的，放两个 3500，三个答辩题。

这个题有一个类似的版本是 https://www.luogu.com.cn/problem/P5912，不同的是那个题是点分树，有 \log 的结论。

这样我们可以得到一个类似的做法：

考虑问题等价于给每条边赋一个权值 v_i，使得两条权值相同的边路径上一定有一条比它更大的边。最小化权值的最大值。

这样我们记 x 的子树中的一个集合 S_x，v\in S_x 当且仅当子树内有一条权值为 v 的边满足它到 x 的路径上没有 >v 的边。（就是一个前缀最大值的树形版本）

那么我们在转移时假如给 (x,y) 的边赋 v^\prime，那么 v^\prime\notin S_y。

然后新的 S_x 就要并上 S^\prime_y，其中 S^\prime_y 是把 <v^\prime 的数去掉再加上 v^\prime 的集合。（这里要检查合法性，S_x 和 S^\prime_y 不能有交）

不难发现每次使得 S_x 字典序最小一定不劣，证明考虑证明决策包含性，和点的版本是类似的。

这样问题转化成如下形式：（注意这里的决策较点的版本复杂多了）

给 deg(x) 个集合 p_{1\cdots k}，决策 q 使得 p_i<q_i，且所有 q_i 不交，最小化 \bigcup q_i。

事实上这个题还是 LOJ 2850，以后再补。

我们从高到低逐位地确定是否可以放 0，确定方法是钦定后面全是 1 看看合不合法。

具体的判断方法是：

维护一个集合 T，初始为全体 p_i。

若答案当前位为 0，那么只要 T 中有此位为 1 的就寄了。

若答案当前位为 1，那么如果 T 中有两个此位为 1 的也寄了。

否则假如有恰好一个 p_x，那么 q_x 当前位一定为 1，我们去掉 p_x 的这一位重新插入 T 中；

否则我们可以删掉最大的一个 p_x，因为 q_x 肯定已经对它构成偏序了。

用 bitset 配合堆维护，单次是 \mathcal O(n\log n\times \frac{n}{w}) 的。

总共 \mathcal O(n^2) 次确定的过程，每次需要 \mathcal O(n\log n) 的检查，总复杂度 \mathcal O(\frac{n^4\log n}{w})，不过至少是多项式做法！

不过这已经足够通过那个 *3500 的原题/se

事实上这个东西可以被实现为 \mathcal O(n^3\log n)，甚至是 \mathcal O(\frac{n^3\log n}{w})。

我们考虑优化这个堆，我们需要找到只保留后 k 位排序后的最大值。

因此我们对每个点和每个 k，对所有 bitset 的后 k 位排序。

对于每个 i，我们把排序结果前 i 大的数扔进一个 bitset 中。复杂度是 \mathcal O(\text{deg}\log \text{deg}\times \frac{n^2}{w})，加起来是 \mathcal O(\frac{n^3\log n}{w})。

找堆顶时我们维护一个 bitset 表示哪些数还没被删过，然后二分一个 i 判断，这样也可以在总时间 \mathcal O(\frac{n^3\log n}{w}) 内找到堆顶。

而维护当前未被删除的元素的或和可以用线段树做（就是把要删除的位置单点修改成全 0）。

一次修改的复杂度是 \mathcal O(\log n\times \frac{n}{w})，所以整个做法复杂度控制在了 \mathcal O(\frac{n^3\log n}{w})，常数不大但是写起来极其阴间。

不过 LOJ 2850 提供了一个 \mathcal O(n^2\log n) 的更优做法。

来看看 LOJ 2850 的题目，大概就是保证 p_i 的总长度是 L，这个做法可以做到 \mathcal O(L\log L)。

首先有一个观察：我们给所有 p_i 降序排序后，一定存在一组最优解满足 q_i 也是降序。否则直接调整即可。

假如所有 a_i=2^{k_i}，那么答案怎么算？不难发现答案就是对 k_i 降序排序之后的 \max \{k_i+i-1\}，这可以拆成 \ge 和 \le 两边来证明。

因此对于一般的 2^{k_i}\le a_i<2^{k_i+1} 的情况，放缩不难发现最高位至少是 \max \{k_i+i\}-1，至多是 \max \{k_i+i\}，只有一的差值。

我们采用如下方式判断选取 h=\max \{k_i+i\}-1 为最高位是否可行。

实现时可以用一个 bool dfs(int mx) 表示判断当前局面用最高位不超过 mx 的能不能合法。

我们找到最小的一个 p 使得 k_p+p-1=h，那么 [h-p+1,h] 中的位全部都要填满。

对于 [1,p) 中的 a_i，它们已经满足条件，我们把它们删去。把 a_p 删去并插入去掉最高位的 a_p，判断：

这样的时间复杂度首先肯定是至多 \mathcal O(L^2) 的，我们考虑优化：

注意到任意时刻的 a_i 一定是最初的 a_i 去掉前缀的若干个 1，所以可能的 a_i 只有 \mathcal O(L) 个，我们可以事先给它们通过基数排序排好序。

这个基数排序的过程有点讲究：我们按长度从小到大遍历所有串，在比较长度相同的串时按后面部分的大小排序。

排完序后上面的所有操作都可以使用线段树完成，这样总复杂度 \mathcal O(L\log L)，Code。

bool dfs(int mx) {
    int h = t[1].v;
    if(h < 0) return true;
    if(h > mx) return false;
    vector<int> vec; find(1, h, vec);
    int p = vec.back(); for(int x : vec) del(x);
    if(nxt[p] <= m) ins(nxt[p]);
    if(dfs(L[p] - 1)) {
        fo(i, L[p], h) ans[i] = true;
        return true;
    }
    if(nxt[p] <= m) del(nxt[p]);
    if(h < mx && dfs(L[p])) {
        fo(i, L[p] + 1, h + 1) ans[i] = true;
        return true;
    }
    for(int x : vec) ins(x);
    return false;
}

我们证明这样的递归轮数以及递归中 [1,p] 这些删除的数个数之和都是 \mathcal O(L) 的。

首先我们证明，假如每次的 mx 都足够大，那么复杂度是对的。

注意到在这种情况下，每个数只会被遍历至多两次（因为第二次一定合法了），所以总遍历长度还是 \mathcal O(L) 的。

而如果 mx 不够大，那一定是 mx=h，分析一下可以知道，递归过程中需要一直保持跳到的点在全局中就是最大值（否则要么不合法回溯了要么脱离 mx=h 的状态了，而一脱离这个状态就不会再回溯到更前面了）。

我们注意到，对于同一个长度的所有字符串，它们的 k_i 相同而 i 互不相同，因此至多有一个是全局最大值。

这样，mx=h 的递归深度是不超过 \max L_i 的。不难发现这样的递归一定是单线然后返回的，我们记这样的过程为一次失败回溯。

对于某个字符串 a_i，我们观察到从它出发的失败回溯只会有一次，因为返回后走下一分枝时自己已经被删掉了。

而由上面的结论这次递归深度至多是 L_i 的，因此递归的总深度是 \sum L_i。

有了这个结论，我们在套路“删除的数个数之和”时就能忽略掉所有递归过程中的 \mathcal O(1) 了。

均摊一下可知，所有上面代码中 if(nxt[p] <= m) ins(nxt[p]); 的贡献是 \mathcal O(n) 的，现在的问题只剩下所有 a_i 整个串的贡献。

对于一个长为 L_i 的非全局最大值的串，它在扫描过程中被扫到只可能是因为它后面有全局最大值。

而它后面至多有 L_i 个全局最大值，因此它至多被扫到 L_i 次（存疑），总复杂度就是 \mathcal O(\sum L_i)。

另一种视角是这个东西的复杂度不高于底下的 fo(i, L[p], h)，所以是 \mathcal O(\sum L_i) 的。

不过有一个简便的避免这种讨论的方法，就是不删除 vec 中的数，而是在求最大值下标时只询问右边的一个后缀（而不是全局），这个东西的复杂度一定是对的。

5.26

已经困死了，场上除了写了 A 啥也没干。

A

对于大小为 n 的数组 a 和大小为 m 的数组 b，令 n\times m 的网格内的格子 (x,y) 的颜色是黑色当且仅当 a_x+b_y\ge 0，否则为白色。

设 ans 为网格内的黑色矩形数。具体地，ans 为四元组 (l_1,r_1,l_2,r_2) 的数量使得 \forall l_1\le x\le r_1,l_2\le y\le r_2，(x,y) 都是黑色。

初始时 a,b 长度都为 1，有 Q 次操作，每次操作向 a 或 b 中 push_back 一个元素，输出新的 ans。

感觉是有些困难的题，场上算贡献算了好久，可能是精力实在太差的原因吧。

总的思路就是考虑一次操作会新增多少贡献。

首先这个东西的形式可以被转化为 \min a_i\ge \max -b_i，假如当前新增一个的下标为 a_r（b 一边是类似的），那么我们要对所有 l 算出：

我们考虑离散化后对每个 k 维护有多少区间 \min_{l\le i\le r} a_i=k。

建出笛卡尔树，设点 x 支配的区间为 [L_x,R_x]，那么对 [x,R_x] 区间内的 r 都会有 x-L_x+1 倍的贡献，贡献在 k=a_x 的位置上。

因此我们这个"有多少区间 \min_{l\le i\le r} a_i=k"可以被简单维护为一个一次函数的形式。

这样，配合线段树可以求出有多少区间 \min_{l\le i\le r} a_i\ge k，我们记 cnt(k)=\sum_{1\le l\le r\le m}[\max_{l\le i\le r}-b_i\le k]。

而这里维护一次函数的一次项系数就是 r=n 的答案，这样就可以维护一个一次函数 f_A 表示假如 n 向右移一格，不考虑新的贡献时答案的差值是多少：

\sum_{l=1}^n cnt\left(\min_{l\le i\le r} a_i\right)

这同样可以维护，复杂度 \mathcal O(n\log n)。

&& B

你可以用如下两种方式合并相邻的数列 l_{1\cdots p} 和 r_{1\cdots q}：

  • 叠置：合并为 [l_1,\cdots,l_p,r_1,\cdots,r_q]。
  • 混合：合并为 [l_1,r_1,l_2,r_2,\cdots,l_p,r_q]。该操作要求 p=q。

给定排列 b_{1\cdots n}，还原出字典序最小的 a，使得 [a_1],\cdots,[a_n] 可以通过 n-1 次合并得到 b。

非常 Ad-Hoc 的一个题，直接贺题解了。

设 solve(b) 为 b 的答案，我们从前至后确定出所有 a_i。

首先对于暴力我们可以考虑搜索，我们考虑倒过来考虑，每次相当于可以把一个数列分成两半或者把一个数量按奇偶分开。

容易观察到此时的所有状态都可以用 b_l,b_{l+k},b_{l+2k},\cdots,b_{r} 表示，这样我们得到了一个多项式做法。

考虑找一点性质以求优化。（上述的所有 k 下文记为 step，避免重名）

首先 a_0=b_0,a_1=\min_{k\in \mathbb N,2^{k}\le \frac{n}{2}} b_{2^k}。若 2^k=1，那么直接令 a[1\cdots n-1]=solve(b[1\cdots n-1]) 即可。

否则 a_0 应当是最早的和 a_1 合并的元素之一，这个“最早”的意思是在所有的混合操作之前。

我们枚举开始混合操作时 a_1 所在段的长度 l^\prime，显然 2\le l^\prime\le \frac{n}{2^k}。

这种情况下生成的 a[l\times 2^k\cdots n-1]=solve(b[l\times 2^k\cdots n-1])，重点是处理前面部分。

我们考虑第一段（也就是 a[1\cdots l^\prime-1]）最后分别在 b[2^k,2\times 2^{k},3\times 2^k,\cdots,(l^\prime - 1)\times 2^k]，所以还原的结果就是它们的 solve。

同样 a[l^\prime,2l^\prime-1] 就是 solve(b[\frac{1}{2}\times 2^k,\frac{3}{2}\times 2^k,\frac{5}{2}\times 2^k,\cdots,\frac{2l^\prime-1}{2}])。

上面就是类似地做上去，因为每次的操作是合并一个段，再和后面的段混合，就是让 l\gets 2l^\prime,k\gets k-1，然后枚举一个新的 l^\prime。

但现在这个东西复杂度依然是错的，因为我们每次都需要枚举这个 l^\prime。

考虑 a[0\cdots l^\prime] 这几位就可以确定出应该选哪个 l^\prime，因为 a[0\cdots l^\prime-1]=solve(b[0\times 2^k,1\times 2^k,\cdots,(l^\prime-1)\times 2^k])，而 a_{l^\prime}=b_{\frac{1}{2}\times 2^k} 是确定的，这样我们其实可以改造一下这个 solve：

这个 solve 表示计算 b[0\cdots len-1] 的答案，如果构造过程中有一位大于一个值 lim（就是上一层递归中的 b_{\frac{1}{2}\times 2^k}）就直接退出，并返回当前构造的数组的长度作为上一层的 l^\prime。

这样我们构造时可以从前往后构造 a，边构造边判断是否大于 lim。

上面的一些细节要经过一点改造，可以写出这样的代码：（注意为了保证 a_1 是准确的，我们在 a_{2\cdots (l^\prime -1)2^k} 这些位置不能判断 lim）

struct node {
    int *v, d;
    node operator+(int k) {  return (node) {v + k * d, d};  }
    node operator*(int k) {  return (node) {v, d * k};  }
    int& operator[](int k) {  return v[k * d];  }
} ;

int solve(int len, node a, node b, int lim) {
    if(len <= 0) return 0;
    if(b[0] > lim) return 0;

    int k = 1; a[0] = b[0];
    for(int i = 2; (i << 1) <= len; i <<= 1)
        if(b[i] < b[k]) k = i;
    if(b[k] > lim) return 1;

    int cnt = 1;
    for(int d = k; d > 1; d >>= 1) {
        // 这里的 a + cnt 是易见的，第一行是选定一个新的 l'，第二行是指定 a[l,2l'-1]
        cnt += solve(len / d - cnt, a + cnt, b * d + cnt, b[d >> 1]);
        cnt += solve(cnt, a + cnt, (b + (d >> 1)) * d, INF);
    }
    // 最后合并的一次
    return cnt + solve(len - cnt, a + cnt, b + cnt, lim);
}

分析一下它的复杂度。每次执行找 k 的过程必然伴随着前面的一个 a[0] 被指定。

而程序逻辑保证了所有递归到的位置 a[0] 互不相等，除非在 if(b[0] > lim) 处就已经返回。

所以 \sum \log k=\mathcal O(n\log n)，这样也解释了下面 for 循环的复杂度，总复杂度是 \mathcal O(n\log n) 的。

* C

(*3500) CF1740I

场上没仔细想，事实上第一步都没想到/cy

第一步是转化为差分，这个思路就是一次操作的数少一定比数多好分析。

然后有一个较为通用的观察：这个操作使得 b_p 自增 x，b_{p+k} 自减 x，因此所有 \bmod k 的同余等价类中和不变。

这样只要所有 \gcd(n,k) 个环中总和 \bmod m\ne 0 就一定不合法。

我们考虑在一个环中，如果有一个点为 p，那么我们枚举 p 给 p+k 传输了多少 x，那么由于我们的目标至少要所有 b_i=0，后面所有操作都是确定的。

这样一个环只有 \mathcal O(m) 种本质不同的操作，我们对于一个长为 L 的环，\mathcal O(m) 地枚举 x 之后 \mathcal O(L) 模拟一遍可以求出最小操作步数。

因为我们的目标不止所有 b_i=0，还需要让 a_0=0，所以我们务必要考虑某个位置的改变量。为了方便不妨分析 k-1 这个位置。

只要操作的 p\in [0,k)，那么 a_{k-1} 就会加上 x。我们在模拟过程中还可以顺便求出 a_{k-1} 的改变量 \Delta。

这样就可以 DP 了，我们记前 i 个环的总 \Delta 为 j 的最小操作步数为 dp_{i,j}，朴素转移可以做到 \mathcal O(nm^2)。

要优化这个过程还需要一些观察，借此把 \Delta 和代价 cost 通过某种关系联系起来，否则没法优化。

我们考虑经过 a_{k-1} 的路径总共有 k 条，它们在每个环中应该是均匀的，因此每个环中应该恰有 c=\frac{k}{\gcd(n,k)} 条。

设一个环中 x=0 时 \Delta=\Delta_0，那么 \Delta_x=\Delta_0-xc。

我们算出所有 \Delta_0 的值后在 a_{k-1} 中加上，可以得到一个 a^\prime_{k-1}，我们就是要求 a^\prime_{k-1}=c\sum x，也即 \sum x=\frac{a^\prime_{k-1}}{c}。

这样限制被转化为对 \sum x 的形式。那么代价呢？

注意到这个代价同样也是 \sum_{i}\min\{A_i-x,B_i-x\} 的形式，它们由 \mathcal O(len) 段等差数列构成。

这样转移的代价就是一个一次函数，可以单调队列优化，这便以 \mathcal O(nm) 的复杂度通过了此题。

5.27

天天模拟赛打你妈！！！

* A

http://www.nfls.com.cn:10611/up/WC2021%E6%A8%A1%E6%8B%9F%E8%B5%9B/day4_p2.pdf

给定 a_{1\cdots n} 表示 i 处矩形的高度，Q 次询问一个区间 [l,r]，求区间内的最大矩形。

放到笛卡尔树上看，答案区间有三类情况：

总复杂度 \mathcal O(n\log^2 n)。

启示：有两维限制的算贡献可以考虑 CDQ，降掉一维。

B

http://www.nfls.com.cn:10611/up/WC2021%E6%A8%A1%E6%8B%9F%E8%B5%9B/day4_p3.pdf

好像绍一模拟赛出过，但我没啥印象了（

赛时嘴巴了一个根号做法，大概就是（利用主席树）建出子序列自动机后，假如从一个状态出发的路径数不超过 \sqrt{k}（称为小状态），那么就把这些路径的信息依次记录下来。

暴力 DFS 整个子序列自动机下去，碰到小状态就直接返回，否则继续暴力 DFS。复杂度是 \mathcal O((n+k)\log a+k\sqrt{k}) 的。

不过经过分析事实上这个 \sqrt{k} 是不必要的，因为搜一次肯定会出来一个答案，复杂度是对的，不用优化。

如果不想写主席树，也有一种使用堆的做法。

本质上我们的问题是求出 k 小值，那么可以用堆配合 RMQ，像 KTT 板子中的那个做法一样记录区间。

注意这个 DFS 过程应该是类似于并行的。

具体可以看

复杂度都是 \mathcal O(n\log n)。

void dfs(ll cur, vector<int> vec) { // x : pre
    int x = *vec.begin();
    if(k == 0 || x == n) return ;
    priority_queue <pair<pair<int, int>, pair<int, int> >,
        vector<pair<pair<int, int>, pair<int, int> > >,
        greater<pair<pair<int, int>, pair<int, int> > > > q;
    vector<int> nxt;
    q.push(make_pair(ST.query(x + 1, n), make_pair(x + 1, n)));
    while(q.size()) {
        int l = q.top().second.first, r = q.top().second.second;
        int v = q.top().first.first, p = q.top().first.second; q.pop();
        for(int j = 0; j < (int)vec.size() && vec[j] < p && k; j++)
            nxt.push_back(p), k--, printf("%lld\n", (cur * B % P + v) % P);
        if(k == 0) return ;
        if(l < p) q.push(make_pair(ST.query(l, p - 1), make_pair(l, p - 1)));
        if(p < r) q.push(make_pair(ST.query(p + 1, r), make_pair(p + 1, r)));
        if(q.empty() || q.top().first.first > v)
            dfs((cur * B % P + v) % P, nxt), nxt.clear();
    }
}

C

http://www.nfls.com.cn:10611/up/WC2021%E6%A8%A1%E6%8B%9F%E8%B5%9B/day4_p2.pdf

我们考虑合并两棵树时需要新计算的只有两树之间的贡献。

拆开所有贡献后，问题转化为对于一棵树 T_i 中的一个点 x，计算 f(i,x) 表示 \sum_{y\in T_i}\text{dis}(x,y)。

计算方式依然是递归，判断 x 在 i 的哪个部分中计算贡献即可。

这又引出了一个需求：要计算某树中两点的距离，这也可以直接实现。

由于所有 m 棵树中每棵树中只有 \mathcal O(m) 个点会产生贡献，状态数是 \mathcal O(m^3) 的，用 map 实现会多一个 \log。

Week 2

5.29

DP 专题训练，记在做题记录中。

不打算全部做完，会扔掉一大部分。

5.30

今天怎么这么困！！

A

(*2900) CF 725 F

比较简单的博弈论，把情况讨论清楚就好了，具体可以看原题题解。

B

(*3300) CF 725 G

单纯的一道答辩题。

把题目理清楚就可以想到按 t_i+dep_{x_i} 升序排序，排完就是简单的数据结构问题了。

写起来有点阴间的。

* C

(*3400) CF 1098 E

这个题甚至还是讲课题，看来我并没有好好听课（

首先我们可以用 \mathcal O(n\log^2 V) 的时间找到 b 中的所有 \mathcal O(n\log V) 个连续段，以下记 m 为连续段数量。

然后二分答案，问题便转化为数有多少个区间和不超过 C。

假如每个连续段长度都是 1，那么直接双指针可以单次 \mathcal O(m) 地直接完成。

因此整个问题肯定也和双指针有关，我们考虑对于值域计算贡献。

假如 a_l=a_r，这部分贡献是好算的。否则记贡献为 f(l,r)，观察可知有一大部分 f(l,r)=0，另一大部分 f(l,r)=cnt_lcnt_r。

这两种的贡献可以简单双指针，我场上不知为何卡在这了。

启示：固定左端点移动右端点 的扩展性不如 同时移动左右端点。

剩下的对数是 2m+\mathcal O(1) 的（而不是固定左端点移动右端点的 m+\mathcal O(1)，所以更强大），可以对于每对 (l,r) 暴力计算。

而此类的 f(l,r) 是一个 Floor-Sum 的形式，可以类欧直接做。复杂度 \mathcal O(n\log^3 V)，其实是能过的。

复习一下 Floor-Sum，答案式子是：

\sum_{i=0}^R\sum_{j=1}^{+\infty}[Xi+Yj\le A]=\sum_{i=0}^R\sum_{j=1}^{+\infty}[Xi+Y(A-j)\le A]=\sum_{i=0}^R\sum_{j=1}^{+\infty}[Xi-Yj\le A(1-Y)]

推这个类欧式子是真的恶心，好像在厕所里耍杂技，拿着个马桶塞子四处倒腾几泡大粪。

5.31

A

(*2800) CF 377 E

简单题，但是场上太困做了好久好久，以后要多睡觉！

& B

(*3200) CF 1037 G

怎么大家都会 3200？？？以后要加训 CF 了！！

首先我们通过推理可以直接得到一个状态数为 \mathcal O(n^2) 的 DP，就是对每个区间计算其 SG 值，简单优化可以做到转移 \mathcal O(n|\Sigma|^2)。

之后的部分需要一个观察，就是说有用的区间只有 \mathcal O(n|\Sigma|) 个。

我们使用记忆化搜索从 [1,n] 递归下去计算的过程中，所涉及到的区间有一个性质：

但是询问不一定只有 [1,n]，这样对于询问区间 [L,R]，递归涉及到的区间除自身外一定也满足：

这样的区间个数是 \mathcal O(n|\Sigma|) 的，具体证明可以考虑对每个字符计算有多少区间这个字符是作为左端点的，每个字符这样的区间数都是 \mathcal O(n) 的。

这样我们对每个这样的区间枚举当前的转移，单次 \mathcal O(|\Sigma|) 地计算 SG 函数，这意味着枚举完转移后我们必须 \mathcal O(1) 得到答案。

这可以利用前缀和完成，具体地假如我们枚举到 [l,r] 区间，枚举字符 c 的首次出现为 p，最后一次出现为 q，那么结果就是三者的异或和。

枚举顺序得是按 r 从小到大，l 从大到小的顺序，这样才能做前缀和。

而 l 是 p 之前出现的第一个 s_{l-1}，记为 f_{p,s_{l-1}}，状态数也是 \mathcal O(n|\Sigma|) 的。

注意这里记录区间切不可使用 map，而是用上面说到的 “i 之后第一个 c” 的形式，总复杂度是 \mathcal O(n|\Sigma|^2+Q|\Sigma|)。

这个题实现好困难，总代码不长但是对我而言细节很多，不知道他们场上怎么写出来的。

const int Sig = 30;
int pre[N][Sig], nxt[N][Sig], lv[N][Sig], rv[N][Sig], sum[N];
int calc(int l, int r) {
    if(l > r) return 0;
    if(l == r) return 1;
    bitset<Sig> vis; vis.reset();
    fo(i, 0, 25) if(pre[r][i] >= l) {
        int p = nxt[l][i], q = pre[r][i];
        int cur = rv[l][i] ^ lv[r][i] ^ (sum[q] ^ sum[p]);
        vis[cur] = true;
    }
    fo(i, 0, 25) if(!vis[i]) return i;
    return -1;
}
void Main() {
    fo(j, 0, 25) pre[0][j] = 0, nxt[n + 1][j] = n + 1;
    fo(i, 1, n) {
        fo(j, 0, 25) pre[i][j] = pre[i - 1][j];
        pre[i][s[i] - 'a'] = i;
    }
    fr(i, n, 1) {
        fo(j, 0, 25) nxt[i][j] = nxt[i + 1][j];
        nxt[i][s[i] - 'a'] = i;
    }

    fo(r, 1, n) {
        int p = pre[r - 1][s[r] - 'a'];
        fr(l, r, p + 1) rv[l][s[r] - 'a'] = calc(l, r - 1);
        if(p) sum[r] = sum[p] ^ rv[p + 1][s[r] - 'a'];
        vector<pair<int, int> > vec;
        fo(i, 0, 25) if(pre[r][i])
            vec.push_back(make_pair(pre[r][i], i));
        sort(vec.begin(), vec.end(), [](pair<int, int> X, pair<int, int> Y) {
            return X.first > Y.first;
        });
        for(auto t : vec) lv[r][t.second] = calc(t.first + 1, r);
    }
    fo(i, 1, Q) puts(calc(q[i].l, q[i].r) ? "Alice" : "Bob");
}

&& C

(*3500) CF 1292 E 加强版

为啥大家都这么会这种题？？？

这个题全靠手玩，是单纯的 Ad-Hoc，个人不赞成把这种题出进区分性的竞赛中，不过我说的也不算数就是了。

有一个朴素的想法，就是每次确定出一个前缀，从这个长为 x 的前缀每次用代价 \frac{2}{(x+1)^2} 延伸一位，总复杂度是 \frac{\pi^2}{3} 的，没啥用。

但是"延伸一位"这个思想是非常重要的，我们考虑假如已经确定出了前 n-1 位，那么确定出第 n 位只用 \frac{2}{n^2} 的代价。

事实上我们可以询问 CH,CO,CC,HO,HH,HC 这六个串，这样只要前 n-1 位中有位置没有确定那么一定是 O。

剩下要确定的就是最后一位了，直接花 \frac{2}{n^2} 的代价确定即可，总代价 1.5+\frac{2}{n^2}。

不过其实还可以再压一个：我们只询问 CH,CO,CC,OH,HH 这五个串，这样不能确定的只有首位的 H / O 和末位的 C / O，直接判断即可。

答案是 1.25 + \frac{3}{n^2} 的，足以通过原题，但是无法通过本题。

本题需要一个小优化：先问出第一位再问最后一位，答案变为 1.25+\frac{1}{(n-1)^2}+\frac{1}{n^2}，足以通过 n\ge 5 的部分。

对 n=4，一个简单的做法是直接搜一个方案出来，状态数不大。

不过也可以手玩出一种做法：

先询问 CH,OH,CO,HH 四个串，如果有至少一个串问到了可以直接 1+2\times (\frac{1}{9}+\frac{1}{16}) 询问出来。（当然也可以搜出所有可能一个一个问过去）

否则询问 CC，如果问到了就搜搜搜，搜出来一个一个问过去，实测可以接受。

再否则中间两位确定为 OO，且头是 H/O，尾是 C/O，可以直接问 OOO 一次确定出来。

鬼知道这是怎么凑出来的。

6.1

儿童节！！！

把之前模拟赛的题补完了，剩了个 5.25 C 没写。

6.2

今天打得没有太烂，但是由于精神不振状态还是很差。

A

HDU 6845

有一些难度的题目。

做法是区间线性基，问题本质上就是倒过来插入一个线性基，基里面每一位有一个归属权，这个权是谁的这位就归谁管。

* B

HDU 6849

场上把做法写复杂了，甚至还要一个线段树维护 DP。

（不过这个东西配合“向上移点”的技巧就可以长剖优化了，新技巧属于是）

我场上是设 dp_{x,i} 为 x 子树内的所有花 y 的 \min\{dep_y-r_y\}=i，不过实际上放宽点限制，设成 \min\{dep_y-r_y\}\ge i 更有利于转移。

但这样写它的正确性就没那么显然了，需要讨论不少细节。

我们把所有 dp_{x,i} 分为两类，一类是 i>dep_x 的，一类是 的。

观察到，我们在把 x 的子树 y 合并进 dp_x 中时假如两边都是 \le dep_x 的那么就不可能有更新。

这样我们用一个 map 去维护所有的 dp_{x,i}，i> dep_x 的部分保证维护的值是单调的，剩余部分就不管了。

这样更新时假如是一个 i\le dep_x 和一个 i>dep_x 合并，那么直接单点更新即可。

否则两边 i>dep_x，一定合法，而且单调加单调还是单调，直接加即可。

使用启发式合并，复杂度是 \mathcal O(n\log^2 n)。

map<int, ll> dp[N];
void dfs(int x, int fa) {
    dp[x][dep[x] + 1] = 0;
    for(int y : g[x]) if(y != fa) {
        dfs(y, x);
        if(dp[x].size() < dp[y].size()) swap(dp[x], dp[y]);
        if(dp[y].empty()) continue;

        dp[x][dep[x] + 1] = max(dp[x][dep[x] + 1], dp[x][dep[x] + 2]);
        for(auto it = prev(dp[y].end()); ; it--) {
            if(next(it) != dp[y].end())
                it->second = max(it->second, next(it)->second);
            if(it == dp[y].begin()) break;
        }

        for(auto t : dp[y]) if(t.first > dep[x])
            dp[x][2 * dep[x] + 1 - t.first] += t.second;
        for(auto t : dp[y]) {
            if(t.first <= dep[x]) {
                int lim = 2 * dep[x] + 1 - t.first;
                dp[x][t.first] = max(dp[x][t.first], dp[x][lim] + t.second);
            } else dp[x][t.first] += t.second;
        }
        dp[y].clear();
    }

    for(auto t : vec[x]) {
        int cur = dep[x] - t.first, lim = 2 * dep[x] + 1 - cur;
        dp[x][cur] = max(dp[x][cur], dp[x][lim] + t.second);
    }
}

** C

HDU 6844

一个非常答辩的题。考虑点分治。

（我觉得考虑到点分治有点难，不过大致逻辑就是这个东西和有根树的 祖先-后代关系 联系不大，就去考虑点分治了）

我们对于点分树上的 x 的子树，如果子树内有两个点 u,v 分别属于不同的 x 的儿子的子树，那么它们一定会经过 x。

对于询问的一对 u,v，我们记答案路径经过的在点分树上深度最浅的点为 x，这样答案就可以被拆成两部分：

由于第二部分是静态的，或许较为简单，我们先考虑第二部分。

这个东西肯定是若干方案取 \min，第一种方案是从 x 不去加油直接到达 v，这部分是平凡的。

别的方案一定要先去加油站，那么答案只和 x 到加油站的距离有关。

我们把子树内的加油站取出按照 c_i 到 x 的距离升序排序（由于点分树树高 \mathcal O(\log n)，所以这部分复杂度也是 \mathcal O(n\log^2n) 的）。

依次访问所有加油站，给所有从这个加油站出发能到达的点取 \min，但是这个怎么实现呢？

不难想到本质上是从这个加油站出发 BFS，而这个加油站的出边相当于是它在树上的一个邻域，可以从点分树上找到！

具体实现可以用 set 等容器实现，总复杂度是 \mathcal O(n\log^2 n) 的。

第一部分其实也是类似的，只不过这个东西要反过来，把上面的 “距离” 都换成 "d_i 减去距离"，其余部分类似处理即可。

启示：邻域查询就点分治！！！和链信息无关也点分治！！！

代码之后再写，先咕着。

6.3

起晚了，没去打模拟赛，咕掉得了。

Week 3

啥时候能回绍兴啊？？？？？

6.5

shaber 树论专题，狗都不写。

6.6

今天整个人状态寄了，真垫底了/cf

A

CF1184D2

Linshey 阴间场，补个 A 得了。

首先非常容易地可以写出一个 \mathcal O(m^6) 的高斯消元做法，方程大致是：

\forall 1<j<i,f(i,j)=\frac{(m-i)(i-j+1)}{m(i+1)}f(i+1,j)+\dfrac{(m-i)j}{m(i+1)}f(i+1,j+1)+\dfrac{i}{m(i-1)}\left(\sum_{t=1}^{k-1} f(i-t,j-t)+\sum_{t=j}^{i-1}f(t,j)\right)

碰到这种有后效性的 DP 式子，第一步要尝试整理出阶段性。

对于这个式子，移一下项就是：

\dfrac{(m-i)j}{m(i+1)}f(i+1,j+1)=f(i,j)-\frac{(m-i)(i-j+1)}{m(i+1)}f(i+1,j)-\dfrac{i}{m(i-1)}\left(\sum_{t=1}^{k-1} f(i-t,j-t)+\sum_{t=j}^{i-1}f(t,j)\right)

可以发现，j+1 的状态只与 j 及之前的状态有关，这样就可以用主元表示法优化消元了。

具体地我们设出所有 f(i,2)=x_i\ (1<i<m)，然后设每个 f(i,j)=\sum_{t}F_{i,j}(t)x_t+C_{i,j} 进行转移。

上面的转移看似是 \mathcal O(n^4) 的，实则可以前缀和优化至 \mathcal O(n^3)。

做完转移后我们要解方程，怎么解呢？这需要一些观察，具体地我们对移项前的式子取 i=m，可得：

\forall 1<j<m,f(m,j)=\dfrac{1}{m-1}\left(\sum_{t=1}^{j-1} f(m-t,j-t)+\sum_{t=j}^{m-1}f(t,j)\right)

把它和上面推出来的 f(m,j) 一等，\mathcal O(n^3) 解个方程，这题就做完了。

（不过可能也不需要什么观察，只是单纯因为这些方程没用到过）

启示：

B

CF1666H

咕。

* C

CF1434E

咕。

6.7

A, B 懒得写了。

C

这题开始就需要一个转化，便于我们把它转为代数形式。

咕。

6.8

润回家了。

Week 4

6.13

今天打得尚可，会了前两个题，只可惜 A 被卡常了。补一下 C。

@ C

先考虑 v=1 的部分。

假如只需要判断一个局面是否先手必胜怎么做？

观察样例，发现大部分情况都是先手胜当且仅当 2\nmid n，但是显然是有特例的，比如先手一步后就可以获胜的情况。

什么情况下会出现 2\nmid n 而先手无法获胜呢？容易发现这种情况下后手的最后一步操作 a_t 一定形成了首个长为 k 的 LIS。

那么前一步先手在干什么呢？假如这个长为 k 的 LIS 经过 a_t，那么我们操作 t-1 时取 a_t 即可避免这样输掉。

换言之，先手只要不断取 S 中最大的数就可以保证自己下一步一定不会因为对方形成了一个长为 k 的 LIS 输，同理对后手也是如此。

因此判断一个局面的必胜性只有两种情况：

怎么判断先手是否可以一步杀？取最大值一定不劣。

回到原问题，这等价于枚举先手的每一步操作然后判断是否必胜，仔细讨论一下可以做到 \mathcal O(n\log n) 的复杂度。

对于 v=2 我们得推倒重来。这部分双方都要尽可能地避免形成新的 LIS。

我们猜测在大范围内依然有先手胜当且仅当 2\nmid n，但是这次的“特例”貌似有点多。

比如，2\nmid n 的情况是否可以导出先手必胜？

答案是否定的，比如说可能在当前情况下，先手无论怎么操作都会使 LIS 长度增加。

我们设当前 LIS 长度为 c，关注 k=c+1 的情况，可以发现这种情况下有好多数被“弃用”。

这提示我们要关注所有长度为 1\le l\le k-1 的最优 LIS（因为它们在后续操作中都可能会变为长为 k 的 LIS），这是比较复杂的。

表示这些数的一个方法是对于每个数 i 去找到一个 d_i 表示以 i 结尾的 LIS 的长度是多少（取前缀 \max）。

可以发现，一次在序列末端加上一个 x 的操作相当于对 [x,n] 中的 d_i\gets \max(d_i,d_x+1)。

假如我们找出连续段之间的“分界线”，也即设 f_x=\min_{d_i\ge x}i，那么这个操作相当于使 f_{d_x+1}\gets x，这是一个类似于阶梯 NIM 的游戏。

但这不完全是阶梯 NIM：它的操作不自由。更加细致的分析可以得到，这个博弈模型在操作时会先把操作的那对石子减一个再向下传。

这里实在不会了，看了题解。

得用找不变量的思想，注意到每两次操作后石子总数的奇偶性不变，且终止态数量为偶数。

那么若 k-1 这堆石头有 \ge 2 个，则必然可以调控使得后手必败，且只有这一种选择。

否则假如要改变奇偶性，我们只能寄希望于从上到下传导下去，但是优势一方可以轻松破坏你的传导。

举个例子，假如当前总和为奇数，那么如果后手搬了一车棋子运到了 k-1 的位置，那么当且仅当棋子数 \ge 2 后手下一步才能运出去至少一个棋子，但是由上面的分析先手此时必胜。换言之，自己想逆天改命，别人比你先赢。

启示：

6.14

今天打得还是很拜登的，B 好长时间都不会。C 是阴间题，就不补了。

** B

这个题好像是由若干套路接起来的好题，别的不说至少 Educational。

直接计算答案过于困难，需要计算贡献。但直接计算贡献不可行（我场上就卡住了），考虑容斥。（这个容斥他妈怎么想到的？）

假如询问区间是 [l,r]，那么对于一个线段树结点 [L,R] 容斥系数是：

这个东西主要是让我们不用注意区分那些不递归到叶子就返回的情况。

这样我们要做的事情就是枚举一个区间 [l,r]，计算出它出现的概率有多大，这东西可以 \mathcal O(n^2) DP。

因此整道题配合前缀和都可以 \mathcal O(n^2) 完成，但依然不够优秀。

然后还需要用到一个“概率双射”（或许可以这么称呼），就是：

感觉这些概率双射很神秘，但是这种东西的证明不是依赖双射的，双射在此是目的而不是手段。

想到这东西的一个主要路径是去考虑分析随机过程，可以把它倒过来变成合并，这样就可以了。

好像很多这种问题都是随机一个排列，这种情况下问题的重点是把局部的问题转为全局的问题。

总之，这样可以推导出 [L,R] 出现的概率。具体地分如下几类：

至此我们已经把所有区间的概率代数地表示出来了。

前两类贡献可以简单特判，后面的贡献可以写成这样的形式：

fo(len, 2, n - 2) fo(lb, 2, n - len) {
    if (l <= lb && lb + len - 1 <= r)
        res = (res + (P - 1) * v[len]) % P;
    else if (lb + len - 1 >= l && lb <= r)
        res = (res + v[len]) % P;
}

通过不等式算出合法的 lb 的界，可以变成 \mathcal O(n) 的含 \min/\max 的和式。

对这个和式大力展开就可以做到 \mathcal O(1)，但是极其阴间。

C

P8861

之后再补。

6.15

计划：

6.16

今天打得还不错，主要失误是 A 多写了一个复杂度错的找环，实际上给仙人掌缩点时直接 Tarjan 跑出来的顺序就是对的。

C 场上没时间做了，赛后补一下。

C

这个东西等价于最小链覆盖，Dilworth 一下就能转化为最长反链。

这样可以证明 n= 2 答案是 \min (h,w)，p_i=2 是 \binom{n}{n/2} 了（后一个用到了 Sperner 定理）。

跑一个二分图匹配可以做 \prod p_i\le 10^3，已经得到 40 分，但是后面的分显然不能如此暴力。

我们考虑扩展一下 Sperner 定理，很自然地我们猜想，最后取出的反链集合是不是可以取 \sum x_i 都相等呢？

打个暴力发现直接过 \prod p_i\le 10^6 了，意外之喜，而且把它改成背包（配合前缀和）可以过 \sum p_i\le 10^6 的包，得到 65 分。

我们考虑证明。首先这肯定是答案的下界，但是关于上界，Sperner 定理的几种常见证法（枚举排列推不等式、调整法）都没法简单推广。

唯一可以推广的是构造性的归纳证明。

此证明基于的一个事实是假如我们把所有点分为划分为互不相交的 d 条链，那么这张图的最小链覆盖不大于 d。

先引入一些定义：

记一个点 (x_1,x_2,\cdots,x_n) 的深度 \sum_{i=1}^n (x_i-1)，记 (p_1,p_2,\cdots,p_n) 深度为 sum。

对于一条非空链 \{A_1,A_2,\cdots,A_k\}，我们称其为对称链当且仅当相邻两点之间深度相差 1，且 A_1 和 A_k 的深度相加等于 sum。

可以发现每条对称链都含有恰好一个深度为 sum/2 的点。

我们证明可以把原图分为若干条对称链，就可以导出原结论。

按 n（而不是 sum）从小到大归纳，n=1 时是显然的。

增加 n 时，我们设原来的链集合为 S_{n-1}，构造一个新的集合 S_n。

生成方法是，对于 S_{n-1} 中的每条链 \{A_1,A_2,\cdots,A_k\}，在 S_n 中加入：

由于 \{A_1,A_2,\cdots,A_k\} 在原先是对称链，容易验证这些新生成出来的在 n 这边也是对称链。

（我们令 (A,x) 表示新生成的点前 n-1 位继承 A，第 n 位是 x）

我们验证一下是否每个点都被覆盖到，对于一个点 (B,x)，考虑 B 所在的链生成出来的新点可知它恰好被覆盖一遍。

至此我们完成了构造，也证明了最初的结论。

此外我们也可以利用单峰对称函数卷积另一个单峰对称函数还是单峰对称函数得到最大值就是 \frac{sum}{2} 的位置，不过这是后话。

剩下的问题就是找到一个不依赖值域的做法了，注意到 n\le 32，那么必然是 meet-in-middle 了。

先看看 n\le 16 怎么做，不难发现这是一个经典容斥，可以 \mathcal O(n2^n) 做。之后部分应该要 meet in middle。

考虑答案是：（其中 f(S) 表示 S 集合中 p_i 之和，m 是 (f(U)-n)/2+n）

\sum_{S} (-1)^{|S|}[f(S) \le m-n]\binom{m-1-f(S)}{n-1}

把 [n] 分为 U_1,U_2，那么答案是：

\sum_{S_1\sube U_1}\sum_{S_2\sube U_2}(-1)^{|S_1|}(-1)^{|S_2|}[f(S_1)+f(S_2)\le m-n]\binom{m-1-f(S_1)-f(S_2)}{n-1}

后面那个组合数必须得拆开来，考虑范德蒙德卷积：

\binom{m-1-f(S_1)-f(S_2)}{n-1}=\sum_{k=0}^{n-1}\binom{-f(S_1)}{k}\binom{m-1-f(S_2)}{n-1-k}

这样枚举完 k 之后两边的组合数独立，而 [f(S_1)+f(S_2)\le m-n] 的限制可以两边排序后双指针。

计算复杂度 \mathcal O(n^22^{\frac{n}{2}})，精细实现应该可以做到 \mathcal O(n2^{\frac{n}{2}})。

6.17

摆烂了，怎么 T1 就是个超纲题，题都不订了。

Week5

6.19

啥也不想干，明天终于要回去了！！！

先补点 NOI 吧。