平凡的做题记录

12.25

P3270 [JLOI2016] 成绩比较

先考虑每个科目课内满足给定要求的成绩方案数，不考虑具体哪些人是哪些人，对于每一个科目，暴力枚举 B 成绩：

\[\sum_{b=1}^U b^{N-R}(U-b)^{R-1} \]

二项式定理暴力拆：

\[\sum_{b=1}^Ub^{N-R}\sum_{j=0}^{R-1}\binom{R-1}{j}(-1)^{R-1-j}U^jb^{R-1-j}\\ \sum_{b=1}^U\sum_{j=0}^{R-1}\binom{R-1}{j}(-1)^{R-1-j}U^jb^{N-j-1}\\ \sum_{j=0}^{R-1}\binom{R-1}{j}(-1)^{R-1-j}U^j\sum_{b=1}^Ub^{N-j-1} \]

最后那个自然数幂和可以拉插。可以做到 \(O(mn^2\log n)\)。

上面部分是独立的一个系数。考虑剩下的部分，恰好转钦定，然后是很平凡的组合数学。懒得写了。

P3643 [APIO2016] 划艇

有：

\[f(i,j)=f(i-1,j)+[a_i\le j\le b_i]\sum_{k=0}^{j-1}f(i-1,k) \]

不难发现按 \(a,b\) 将值域分为至多 \(2n+1\) 段后，每一段内都是一个多项式，一个段被操作一次后阶数至多增 \(1\)，直接拉插可以做到 \(O(n^3)\)。

反正我会被洛谷 \(1s\) 时限卡常。以后练到组合数再补得了。

AT_abc212_h [ABC212H] Nim Counting

先手能赢当且仅当所有堆石子数异或和非零。有 DP：

\[f(i,j)=\sum_{k=1}^K f(i-1,j\oplus A_k) \]

简单改写：

\[f(i,j)=\sum_{k=0}^{2^{16}-1}f(i-1,j\oplus k)cnt_k\\ f(i,j)=\sum_{a\oplus b=j}f(i-1,a)cnt_b=\sum_{a\oplus b=j}f(i-1,a)f(1,b) \]

发现是个异或卷积形式。考虑 FWT。由 FWT 的线性性，所求即为：

\[\mathrm{IFWT}(\sum_{i=1}^n\mathrm{FWT}^i(f)) \]

等比数列公式直接套即可，注意特判 \([i]\mathrm{FWT}(f)=1\) 也就是公比为 \(1\) 的情况。

12.27

P4336 [SHOI2016] 黑暗前的幻想乡

观察数据范围不难想到应该是个状压。

每个公司恰好负责一条路太难搞了，发现可以转化为每个公司都有负责。这个就很好容斥了。

具体的，枚举钦定哪些公司不负责，然后只把要负责的公司的边加进去，跑矩阵树定理即可。\(O(2^nn^3)\)。

P3317 [SDOI2014] 重建

注意是恰有 \(n-1\) 条边存在，因此我们要求的实际上是：

\[\sum_T\prod_{e\in T}p_e\prod_{e\not\in T}(1-p_e) \]

推一下式子：

\[\sum_T\prod_{e\in T}p_e\frac{\prod_e(1-p_e)}{\prod_{e\in T}(1-p_e)}\\ \prod_e(1-p_e)\sum_T\prod_{e\in T}\frac{p_e}{1-p_e} \]

对后面那个跑矩阵树定理即可。但是 \(p_e=1\) 时这个式子会出问题，我们令所有 \(1-p_e\) 加上 \(eps\) 即可。

CF917D Stranger Trees

首先套路地恰好转钦定，考虑如何求钦定 \(k\) 条边重合的方案数，很巧妙的是这个恰等于 \(n-k\) 个连通块生成树的方案数。

然后一个很经典的式子是求 \(n\) 点 \(k\) 个连通块生成树方案数，其中 \(a_i\) 表示第 \(i\) 个连通块的点数：

\[n^{k-2}\prod_{i=1}^ka_i \]

这时候已经可以 \(O(n^3)\) 树上背包了。但还可以继续优化。

考虑 \(\prod a\) 这个东西的组合意义，发现等价于每个连通块内选一个点的方案数，于是可以设计 DP \(f(i,j,0/1)\) 表示点 \(i\) 子树内有 \(j\) 个连通块且 \(i\) 所在连通块选没选点的方案数。转移显然。于是就做到了 \(O(n^2)\)。

01.02

AT_abc253_h [ABC253Ex] We Love Forest

平凡的图计数。

不难想到可以转化为求对应边数的森林方案数，不难想到状压。记 \(g(i,S)\) 表示点集 \(S\) 产生的边数为 \(i\) 的森林方案数。

不难想到可以枚举 \(\mathrm{lowbit}(S)\) 所在的树转移。所以只需要考虑如何求一个集合的生成树方案数即可。

首先直接上矩阵树定理就做完了，但都图计数了显然没必要。不难想到仍然可以枚举 \(\mathrm{lowbit}(S)\) 所在的树 \(T\)，然后将 \(T\) 与 \(S\setminus T\) 合并起来，相当于是枚举断的那条边。那么一棵树显然会被其 \(sz-1\) 条边都计算到，得到的结果除以 \(|S|-1\) 即可去重。

01.03

QOJ14718 Meeting for Meals

不难想到，在保证仍然能在时限 \(T\) 内走到 \(1\) 点的限制下，只需要最小化相遇时间即可，剩下的时间可以全部用以陪伴。

枚举点是不好做的。考虑枚举相遇点，也就是相遇点所在的边。端点相遇的情况同样视作在边上相遇。

假如我们已经有了两个要相遇的点 \(a,b\)，分别走向端点 \(u,v\)，那么只需要满足 \(\min(dis_{a,u}+w+dis_{v,1},dis_{b,v}+w+dis_{u,1})\le T\) 即可，此时相遇时间为 \(\frac{dis_{a,u}+w+dis_{b,v}}{2}\)。不难想到可能有不合法情况，但不合法不优。

实际上，对于一条边，只需要考虑距离其两个端点各自最近的起点即可。倘若一侧有距离更大的点，其与那一侧距离最近的点在别的边相遇不劣。倘若一侧有多个距离相同的点，对于来自不同边的，会在其来自的边算，来自相同边的，显然应当在那条边的另一侧相遇。

故而只需要跑一遍多源最短路然后直接做即可。

QOJ4218 Hidden Graph

关键在于“每个导出子图都存在一个节点度数不超过 \(k\)”的作用。

事实上，这句话等价于可以将每个导出子图分成至多 \(k+1\) 个独立集。构造的话，每次删除度数最小的点，先给剩下的图染色，然后给这个点染色，最后颜色数必然不超过 \(k\)。同时这个构造还表明边数上界是 \(nk\) 的。

故而我们顺次加点，对原来的导出子图每个独立集所有点和新增点放一起问一遍，有边就删掉对应点再问，问到没有边为止，就可以得到新的导出子图的所有边，然后重新染色即可。这样每条边都会被问一次，每个独立集每次都会被额外问一遍，故而查询次数不超过 \(nk+n(k+1)=2nk+n\)。

CF1033E Hidden Bipartite Graph

考虑维护当前左侧点集和右侧点集，因为图连通，因此每次都找一个新的与左侧点集有连边的加入右侧点集或者反之。找的话直接在空闲点集序列上二分就行，由于要减去那个点集内部的边才能得到是否有连边，这一步查询次数是 \(2\log n\) 的。

考虑什么时候会出问题，其实就是将要加入那个点集发现和那个点集有连边的时候，那么同样地一次二分找到那个有连边的点就行。

考虑如何找奇环，实际上只需要找到当前这两个点之间的一条路径即可。故而每次加点时反向二分搜一个对侧点集中与之相连的点存边，这一步由于是独立集因此查询次数只用 \(\log n\)，找的时候直接爆搜即可。

我实现的查询次数大致在 \(3n\log n+3n+\log n\)，可过。

P2766 最长不下降子序列问题

第一问的话直接 DP 就行。

后两问考虑网络流。首先为了保证每个点只用一次先拆个点，然后 \(a_j\le a_i\land f_j+1=f_i\) 的直接连边即可。第三问把相应的四条边流量改做正无穷即可。

注意特判 \(s=1\) 的情况。直接跑会跑出 \(+\infty\)。

01.04

CF1630F Making It Bipartite

首先整除是一个偏序关系，故而图为二分图，当且仅当所有点要么只有入度，要么只有出度。

我们将每个点拆成两个，分别表示其只有入度和只有出度的情况，然后在所有冲突的情况之间连边，这样我们只需要求出这个图的最大独立集即可。可惜的是，一般图的最大独立集不可做。

但是，由 Dilworth 定理，偏序集的最大反链长度等于最小链覆盖。因此，如果我们生成的图也是一个偏序集，就可以网络流跑最小链覆盖解决这个问题。

因为原图就是一个偏序集，故而我们如下构造即可：记 \(i\) 表示只入 \(i'\) 表示只出，首先 \(i\to i'\)，若原图有边 \(i\to j\)，连接 \(i\to j,i'\to j'\)。本来还应连接 \(i\to j'\)，但是因为已有链 \(i\to i'\to j'\) 故而可以省略。

调和级数得边数是 \(O(n\log n)\) 的。网络流跑最小链覆盖是在二分图上跑，故而最后复杂度 \(O(n\sqrt n\log n)\)。

01.05

AT_agc029_f [AGC029F] Construction of a tree

首先有个很神秘的转化，将原点作为左侧点，给定点集作为右侧点，若 \(a\in B\) 则连接 \(a\leftrightarrow B\)，那么能形成一棵树的必要条件为去除任一左侧点后均存在完美匹配。因为除了树根外每个点均可与其父边匹配。

其次任选一些点集，其包含的点的并集大小必然大于点集个数，否则这几条边要么连出重边要么连出环，不合法。

故而我们先任意选一组匹配，从根节点开始搜索，每次找一个与之匹配的点集中包含当前点的未在树上的点作为当前点的子节点。任意时刻，已选的左侧点数量恰为已选的右侧点数量加一，此时未选的左侧点数恰等于右侧点数，故而假如搜不到全部点就必然无解。

QOJ10045 Permutation Recovery

首先排列 \(\pi\) 的逆排列 \(\sigma\) 满足 \(\sigma(\pi(i))=i\)。同理 \(\pi(\sigma(i))=i\)。

那么第 \(i\) 列有个数 \(j\) 的话第 \(j\) 列必然有个数 \(i\)，且他们属于一对排列和逆排列。如果将 \(i\) 和 \(j\) 连边，那么一对逆排列可以表示为多个环，满足每个点都出现了恰好一次。

不难想到我们其实可以每次都找出一对合法排列，然后删去相应点，剩余部分是子问题。

考虑怎么找一些环恰好覆盖所有点一次，不难想到上述条件等价于每个点的入度与出度均恰为 \(1\)，假如我们给所有边定向，那么只需要拆点后将入度点和出度点一一匹配即可。问题在于如何定向使得保证存在完美匹配。

令当前还有 \(k\) 对排列，那么每个点都有 \(2k\) 条边，存在欧拉回路。那么我们直接按照欧拉回路去给边定向，那么每个点的入度与出度均为 \(k\)，由 Hall 定理必然存在完美匹配。

SP4063 MPIGS - Sell Pigs

小清新建模题。直接建分层图按题意模拟跑最大流是简单的，但是太劣过不了。问题在于如何高效处理每次可以调整打开的猪圈这个条件。事实上这个条件等价于，若当前人打开的猪圈之前已经有人打开过，那么相当于当前人可动猪数量可以从那个人处拿一点来。这样建模即可做到点数 \(O(n)\) 边数 \(O(nm)\)。

01.06

P8456 「SWTR-8」地地铁铁

首先对于一个点双，假如其中同时存在黑白边，那么所有点对均可，吗？并非。倘若只有两个点同时有黑白两种点双内连边，那么这两点之间不存在符合条件的路径。特判这种情况即可。

接下来考虑点双间问题，显然只要两点间经过的点双既存在黑边又存在白边即可，建个圆方树然后简单 DP 一下。

然后有个小问题是如何判断一条边属于哪个点双，在圆方树上其连接的两个圆点距离必然为 \(2\)，故而对每个点存个父节点然后判一下即可。

AT_agc038_f [AGC038F] Two Permutations

不难发现对于每个置换环，要么整个变成自环，要么保持不变。那么考虑网络流。

\(x\) 向 \(y\) 连边可以使得 \(x\in S\land y\in T\) 时额外产生边权大小代价。向源点汇点连边作用显然。

直接大力分讨。然后发现有“两个状态相同产生代价”这种东西实现不了，直接反转 \(B\) 类置换环属于左右侧的意义即可。

01.08

AT_arc147_d [ARC147D] Sets Scores

由于相邻集合只有一个元素的状态会发生变化，因此可以使用初始集合和操作序列唯一表示一个集合序列。

对于初始集合计数有些复杂，考虑对于操作序列计数，那么每个元素的贡献只在于其是否位于初始集合中，并且两种情况各自的贡献 \(a,b\) 之和恰为 \(n\)。那么这个操作序列对于所有初始集合的答案可以表示为 \(\prod_{i=1}^m(a_i+b_i)=n^m\)。

于是只需要计算操作序列的个数即可。答案即为 \(m^{n-1}n^m\)。

P4351 [CERC2015] Frightful Formula

硬拆柿子没有前途。考虑转化为格路计数问题。相当于是向右走贡献乘上 \(a\)，向下走贡献乘上 \(b\)，每个点额外产生 \(c\) 的贡献。

首先忽略加的 \(c\)，每个起点的贡献是好做的，路径方案直接组合数易求，然后向下走和向右走的步数一定所以 \(a,b\) 次数一定，可以直接算。

然后考虑加的 \(c\)，它们的贡献显然为：

\[\begin{aligned} &c\sum_{x=2}^n\sum_{y=2}^n\binom{n-x+n-y}{n-x}a^{n-x}b^{n-y}\\ =&c\sum_{i=0}^{n-2}\sum_{j=0}^{n-2}\binom{i+j}{i}a^ib^j\\ =&c\sum_{k=0}^{2n-4}\sum_{i=\max(k-n+2,0)}^{\min(k,n-2)}\binom{k}{i}a^ib^{k-i} \end{aligned} \]

考虑拆成 \(i\le n-2\) 和 \(i>n-2\) 两部分计算。对于第一部分，是标准二项式定理形式，即为：

\[c\sum_{k=0}^{n-2}(a+b)^k \]

对于第二部分，我们记 \(f(k)=\sum_{i=k-n+2}^{n-2}\binom{k}{i}a^ib^{k-i}\)，则答案为 \(c\sum_{k=n-1}^{2n-4}f(k)\)。\(f(k)\) 是可以递推的，我们利用组合数递推公式拆开组合数就可以得到：

\[\begin{aligned} f(k)&=\sum_{i=k-n+2}^{n-2}(\binom{k-1}{i}+\binom{k-1}{i-1})a^ib^{k-i}\\ &=b\sum_{i=k-n+2}^{n-2}\binom{k-1}{i}a^ib^{k-1-i}+a\sum_{i=k-n+2}^{n-2}\binom{k-1}{i-1}a^{i-1}b^{k-1-(i-1)}\\ &=bf(k-1)-\binom{k-1}{k-n+1}a^{k-n+1}b^{n-1}+af(k-1)-\binom{k-1}{n-2}a^{n-1}b^{k-n+1}\\ &=(a+b)f(k-1)-\binom{k-1}{n-2}(a^{n-1}b^{k-n+1}+a^{k-n+1}b^{n-1}) \end{aligned} \]

然后就 \(O(n)\) 做完了。

AT_arc139_d [ARC139D] Priority Queue 2

\[\sum\sum_{i=1}^na_i=\sum\sum_{i=1}^n\sum_j[a_i\ge j]=\sum\sum_j cnt(a\ge j) \]

首先加入一个数，如果加入的数 \(\ge j\)，那么 \(cnt\) 加一。否则不变。

然后删除第 \(x\) 小的数。若 \(cnt> n+1-x\)，\(cnt\) 减一，否则不变。

然后我们枚举加一的次数 \(i\)，方案数显然为 \(\binom{k}{i}(m-j+1)^i(j-1)^{k-i}\)。考虑结果。倘若初始时 \(\le n+1-x\)，那么最多加到 \(n-x+1\)。倘若初始时 \(> n+1-x\)，那么加了不动不加就减，减 \(k-i\) 次，最多减到 \(n-x+1\)。

CF1097G Vladislav and a Great Legend

首先普通幂转下降幂。

\[f(X)^k=\sum_{i=1}^k{k\brace i}\binom{f(X)}{i}i!\\ \sum_Xf(X)^k=\sum_{i=1}^k{k\brace i}i!\sum_X\binom{f(X)}{i} \]

考虑 \(\binom{f(X)}{i}\) 的组合意义，实际上就是在这棵虚树上选 \(i\) 条边的方案数。不难想到树上背包。设计 \(f(x,i)\) 表示考虑 \(x\) 子树选了 \(i\) 条边且虚树非空的方案数。

虚树不同的话就在于各个节点的实虚状态。可以先只考虑当前连通块非空转移，然后额外加上当前连通块为空时与这个子节点单独连接的方案。这样的话答案应当在算后者之前计算。

然后上界要卡死，枚举到 \(\min(sz,k)\)，这样复杂度是 \(O(nk)\) 的，可以视作每个块最后 \(k\) 个点与下一个块最前面 \(k\) 个点处理，因此每个点只会和前后 \(2k\) 个点处理。

01.10

BK51291 「NOI2024 省选OIFC模拟20」侏儒的把戏

转化限制可以得到两个红紫区间有交就合法，单步容斥考虑完全不交的好做些。那么贡献当且仅当 \(b<c\or d>a\)。

对每个紫确定其在第几个红之后即可唯一确定序列，考虑 \(f(i,j)\) 表示第 \(i\) 个紫点在第 \(j\) 个红点之后的答案，容易对每个状态得到被上面的贡献的值，记贡献值为 \(v_{i,j}\)，有：

\[f(i,j)=\min_{j'\le j}f(i-1,j')+v_{i,j} \]

考虑整体 DP，那么就需要维护两种操作：每个值变为前缀 \(\min\)，以及区间加。线段树乱打 tag 维护即可。

BK51290 「NOI2024 省选OIFC模拟20」树多

单步容斥转化为求所有树上都不在两点路径上的点数。如果以这样一个点为根，路径两个端点必然全都在同一棵子树上。

于是不难考虑哈希，先给每个树一个随机哈希值，然后对每个点存其以各个点为根时在每棵树中的子树信息集合，对一对端点，一个第三点能贡献答案仅当两个端点在以他为根时的哈希值完全相同。

空间有点炸，逐棵树处理即可。

P7735 [NOI2021] 轻重边

一个比较巧妙的事情是你只需要每次给一操作这条链上的点全部变成一个新的颜色，然后区间查询多少条边两个端点同色即可。容易树剖实现，就是码量大了点，常数也大了点。

01.12

CF1810G The Maximum Prefix

一开始往格路计数方面思考，但只能得到一个 \(O(n^3)\) 的东西，优化失败。

考虑设计 \(f(i,j,0/1)\) 表示前 \(i\) 个，当前前缀和离钦定值还差 \(j\)，是否达到过钦定最大前缀和，的价值之和。初始时 \(f(0,i,[i=0])=h_i\)。这样就能直接 \(O(n^2)\) 搞了。

反转状态后合并多次转移的思路貌似比较有启发意义。但我没想出来就是了。

AT_agc061_c [AGC061C] First Come First Serve

不难想到一对 \(A_i,B_i\) 没有区别当且仅当他们中间没有任何人签名。考虑反向容斥一下，减去中间没有任何人签名的方案数即可。

但是这很不要做，因为中间会存在 \(A_k\in(A_i,B_i)\) 使得 \(k\) 在 \(i\) 后面算。我们考虑贡献延后计算，在最后一个满足上述条件的 \(k\) 处再减去 \(i\) 中间全为空的方案数，此时从第一个 \(B_j>A_i\) 的 \(j\) 到 \(k\) 的选择都是一定的，故而算重的方案数恰为 \(f_{j-1}\)。而对于 \((i,k)\) 之间的 \(f\)，可以视作默认其后面的 \(k\) 选了 \(A_k\)。

这样最后算到 \(n\) 时所有延后的贡献均被算入，答案正确。双指针一下即可。

AT_abc290_h [ABC290Ex] Bow Meow Optimization

我们可以调整法得到如下贪心策略：

• 对于同一个物种，他的排列必然呈单峰状。
• 显然会从整个序列的中间开始往两边填。
• 假如猫狗都是偶数个，那么序列的一半会有恰好一半只猫和一半只狗。
• 假如有一个是奇数个，那么把那个里面最大的放整个序列中间。如果两个都是奇数个，那么把两个里面各自最大的放中间贴贴显然也是不劣的。
• 记每个点的 \(|x-y|\) 为 \(d\)，那么由于另一侧点数一定然后在一侧内临项交换 \(d\) 和不变，故而 \(\sum d\) 一定。
• 故而我们尽可能给 \(a\) 大的最小化 \(d\) 即可。

那么我们按代价从大到小放动物，狗尽可能放左边，猫尽可能放右边，就行了。

01.13

CF1175G Yet Another Partiton Problem

记区间 \(\max\) 为 \(m\)，则区间贡献可以大体写成：

\[f(l-1)-lm+rm+m \]

考虑维护 \(m\)，一个经典的想法是暴力搞，单调栈维护 \(\max\) 区间，这样总入栈出栈次数是 \(O(n)\) 的。出栈不好搞，因为 \(m\) 不降但是我们要求最小值因此不合法情况可能更优必须剔除，但可以线段树分治再套一个 \(\log\) 解决。关键是入栈，我们发现这等价于动态求一个区间的线段关于一个点的最小值，维护困难。

瓶颈就在于如何处理这个 \(m\)。暴力搞不行的话考虑 CDQ，这样一个 \(m\) 就可以拆成左半区间的后缀 \(\max\) 和右半区间的前缀 \(\max\) 取 \(\max\)。假如我们从右往左枚举右侧点，那么右侧前缀 \(\max\) 单降，不难双指针维护首个后缀 \(\max\) 小于当前右部点的前缀 \(\max\) 的左部点位置。

首先左部点首次露出水面之后后面就不用管了，这样一共会有 \(O(m-l+1)\) 次插入；然后是左半边连续一段在水平面下的部分，我们考虑直接找出一个最优位置代表一个区间，此时 \(m\) 相同所以也可以转化为给定线段区间找特定坐标最小值问题，但因为必然是后缀，因此考虑离线下来直接上李超树可以解决，那么每个右部点同样对应一次插入，一个区间共插入 \(O(len)\) 次。因为 \(m\) 比之前小所以必然更优不用删之前的不合法情况

注意李超树插入及清空需要精细实现防止复杂度假掉。大概是 \(O(kn\log^2 n)\) 的。常数略大但很可过。

01.15

P9132 [USACO23FEB] Watching Cowflix P

首先一个关键性质是距离小于 \(k\) 的必然在一个连通块。可以想到调和级数然后上虚树，但是反正我不知道怎么在正确复杂度内每次找哪些点对要被合并。

考虑 \(k>\sqrt n\) 时连通块数不超过 \(\sqrt n\) 个，所以对这一部分可以直接跑 \(O(n\sqrt n)\) 的树上背包。然后 \(k\le sqrt n\) 的部分直接跑 \(\sqrt n\) 次 \(O(n)\) 的 DP 即可。

\(k\) 大的部分要卡空间，用 vector 存用完清空即可。\(k\) 小的部分要卡时间，倒 DFS 序枚举并让每个点给父节点贡献而非父节点枚举子节点贡献即可。

P9333 [JOIST 2023] 议会 / Council

不难发现主席选定时，由于副主席只会给每个议案带来至多 \(1\) 的影响，故而我们其实只关心那些此时票数恰为 \(\lfloor \frac{n}{2}\rfloor\) 的议案。考虑状压，只需要找到与这个集合交集最小的人即可，也就是找到一个人使得其反集与这个集合交点最大。由于主席与副主席不能是同一个人，因此要存次小值。

考虑高维前缀和解决。每个点初始状态在于其是否为一个给定集合的子集，先高维后缀和处理出来即可。

AT_agc039_e [AGC039E] Pairing Points

不难发现，对于每个方案，必然存在一个操作顺序，使得每一条边恰好与之前的一条边相交。否则必然不合法。

我们枚举点 \(n\) 连向的点 \(k\)，那么现在就要求 \([1,n-1]\) 的合法情况。

我们记 \(f(l,r,k)\) 表示区间 \([l,r]\) 只有点 \(k\) 向区间外连了边的方案数。考虑转移，不妨枚举一条跨越 \(k\) 与外界连边的边 \(x\leftrightarrow y\)，满足区间中其他边均在 \(x\leftrightarrow y\) 下面，也就是说区间内所有连边中 \(x\) 最接近 \(l\)，因为不能有环所以区间内不存在别的边与之相交。

我们不妨再枚举 \(s,t\)，满足 \([l,s]\) 只有 \(x\) 向外连了边，\([t,r]\) 只有 \(y\) 向外连了边。那么这时候就拆成了三个独立的区间，有转移 \(f(l,r,k)=\sum f(l,s,x)f(s+1,t-1,k)f(t,r,y)\)。

暴力 \(O(n^7)\) 做即可，由于带了 \(\frac{1}{7!}\) 的常数所以很可过。

01.18

P13782 [eJOI 2022] Where Is the Root?

不难发现所有叶子的 LCA 必然是根节点。于是我开始每次选叶子然后动态删点集维护树形态写了一坨又一坨最后落入始终错一个点然后去世的坏结局。

事实上理一下可以得到：

• 假如根是叶子，只需二分根所在位置即可，用其他任意两个叶子去判断。
• 假如根不是叶子，那么同样地二分根的位置即可，直接拿所有叶子节点去判断。

然后就做完了。可以按度数排序然后直接合并成一个二分。最悲惨。

CF1060F Shrinking Tree

考虑一个点留下来，当且仅当与其有关的所有操作都保留了他。

考虑枚举留下的点。考虑他与一个子节点合并，那么合并之前，这棵子树内可以任意操作，因为我们不在意子树合并前的根节点是多少，但合并之后，这棵子树内所有和根节点的操作都必须保留根节点。

于是我们考虑 \(f(x,i)\) 表示子树 \(x\) 最后 \(i\) 次操作保证根节点不变的方案数，其中被钦定保留的操作自带 \(\frac{1}{2}\) 的系数，那么答案即为 \(\frac{f(rt,n-1)}{(n-1)!}\)。

考虑如何转移，我们先将父边考虑入子节点的方案，对于最后 \(i\) 次操作保留的方案，枚举合并父边在倒数第 \(j\) 个位置操作。若 \(j\le i\)，只需要满足合并后的操作保留父节点即可，同时钦定合并操作的保留点，则贡献为 \(\frac{1}{2}f(x,j-1)\)；否则贡献为 \(f(x,i)\)。

更新完子节点的答案后合并是简单的，直接树上背包，转移的话考虑将两个保留部分混一块、不保留部分混一块，两个简单可重集排列方案数做完了。

简单优化可以做到 \(O(n^3)\)，但 \(O(n^4)\) 很可过。

01.19

CF1442D Sum

等价于，每个序列选一个前缀，使得长度和恰为 \(k\)，求最大价值。

首先有个暴力 DP，\(f(i,j)\) 表示考虑了前 \(i\) 个序列选了 \(j\) 个物品的最大价值：

\[f(i,j)\gets \max_{k=0}^{\min\{j,t_i\}} f(i-1,j-k)+s_k \]

也就是进行一次 \((\max,+)\) 卷积。有点像闵可夫斯基和，可惜凸性不符合。

发现关键结论：至多只有一个序列没有填满，可以调整法证明。

那么现在所有填满的序列都可以单次 \(O(k)\) 转移，然而没填满的序列与之前的序列合并还是 \(O(k^2)\) 的。如果能将没填满的序列作为第一个，然后用填满的序列去转移他，就能做到 \(O(nk)\) 了。

那么考虑分治，每次从未填满的序列存在的一侧向另一侧逐个转移，两种情况取个更优值即可。于是 \(O(nk\log n)\) 解决了。

P13552 鱼类考古学

发现 \((a+b)\& c\le c\le(a\&b)+c\)。所以一操作显然放在最前面最优。

考虑次数是 \(n-k\) 这种奇怪形式，尝试理解出题人意图，可以等价为将原序列划分做 \(k\) 个不交子集使得集合按位与之和最大。

从高位到低位考虑，对于最高位，如果 \(1\) 的个数小于组数，那么每个 \(1\) 单独分一组显然最优，可以调整法证明；否则，所有零必然合成一组（注意也可能有为一的在之后合并进来），合并之后递归考虑即可，同样可以调整法证明。逐位处理贡献即可。