UOJ Logo Rainbow_sjy的博客

博客

UOJ Round #30 题解

2025-05-10 23:53:45 By Rainbow_sjy

赛场设计

idea, solution, std, data by pp_orange

我们称“ a 不能到达 bb 不能到达 cc 不能到达 a”为反三元环。

由于图是一个 DAG,所以对于任意一对节点 (u,v) 必然有 u 不能到 vv 不能到 u 中的至少一个。如果我们建立一张新图,把所有不可达关系全部画到这个图上,我们会发现这个图比竞赛图还密集。一些竞赛图的结论在这个图上仍然成立:

1、我们把这个图缩点之后会形成一个链。

2、这个图大小 3 的 SCC 一定存在三元环。也就是原题中的反三元环

所以缩点后一定会形成一个每个 SCC 大小都小于等于 2 的链结构。

考虑设计 dp[i][j] 表示一共放了 i 个点,链最后一层有 j 个点的方案数,其中 1j2,我们考虑先把 i! 除掉,最后再乘回去即可,转移如下:

dp[i+1][1]dp[i][1]×2i1+dp[i][2]×2i2

dp[i+2][2]dp[i][1]×22(i1)+dp[i][2]×22(i2)

事实上我们还可以更进一步,把 2i(i1)2 也除掉,这样转移就是常系数的线性齐次转移了,可以用矩阵乘法优化。当然,在这个题没有必要,我们的瓶颈在于求阶乘。

这个题还有一些从最长反链 2,于是最小链覆盖小于等于 2 的角度来刻画这个结构的,这里不多赘述。部分分设计主要为了一些指数级、高次多项式复杂度和固定模数算法。

最后复杂度为 O(n)O(nlogn)(快速阶乘算法)。

交通管制

idea, solution, std, data by chenxinyang2006

考虑这样一个问题:假设给原图所有子集 SU 均赋了权重 aS,并定义一张连通子图的权值是其所有边双对应的 a 之积,并且我们还已经对所有 S 知道了 S 的边双连通边子图数量是 bS,如何求原图所有边子图的权值和。

如果已经确定的边双给出的对 U 的集合划分,把每个边双缩为一个点后,这一方案的 a 之积是确定的,各个边双内部的连边方案数是对应的 b 也是确定的,而边双之间的连边方案数相当于做生成树计数。不过如果这样看待问题并不好优化。

我们分阶段考虑这个问题,设 p0pnn 个集合幂级数,(pi)S 表示 S 的导出子图的所有满足 只存在两端编号最大值不超过 i 的割边 的边子图的权值和。最后希望计算 pn,而 p0 因为不允许出现割边, (p0)S=aSbS

考虑 pu1pu 的变化:现在允许点 u 的邻边有割边(但边的另一侧编号仍需 <u)。如果将所有两端编号最大值为 u 的割边断开,这张边子图将会分裂成若干连通块,根据连通块给出的点集划分设 S=PT1T2...Tk,其中 uP,所有 P,Ti 两两无交。那么这张边子图在所有 PTi 的部分都符合 pu1 的限制,这是递归到子问题的形式,并且这个划分当然是唯一的。

于是要计算 (pu)S 只需枚举 S 像这样的集合划分,对应的所有边子图权值和是 (pu1)Pi=1k(pu1)Ticof(u,Ti),其中 cof(u,Ti) 表示选一个 vTi,v<u 新连上 (u,v) 这条子图中的割边的方案数,其实也就是原图中 u 与多少在 Ti 内且编号小于自己的点有连边。

那么设 (qu1)S=[uS](pu1)Scof(u,S),在只考虑 uS 的项的意义下,pu=pu1×(expqu1)。注意若 uS 那么上述分析其实都无效,但当然 (pu)S=(pu1)S

于是计算 n 次集合幂级数 exp 以及子集卷积即可解决上述问题。

称该由 p0 计算 pn 的操作为 “边双连通-连通变换”。


接下来考虑 数边双连通子图,注意在上述问题中若取所有 aS=1,计算出的 (pn)S 应为 S 导出子图的连通边子图数,这可以 Θ(2nn2) 计算。注意上述过程是可逆的,知道 pi 同样只需进行一次集合幂级数 exp 和一次子集卷积即可求出 pi1。于是逐步倒推,在已知 pn 的前提下进行 n 次集合幂级数 exp 以及子集卷积可以倒推得到 p0,称为反向的 “边双连通-连通变换”。


对于本题,限制相当于是一些点对必须连通,以及一些点对的边简单路径必须不唯一。方便起见我们先假定要求选出的边子图连通。

注意到若一个点对已经连通,其间的边简单路径唯一充要于将每个边双缩为点之后,在得到的边双树上两个点简单路径上经过的边双大小均为 1。那么对于确定的边双树,称大小 >1 的边双为黑点,大小 =1 的边双为白点,u,v 间只存在一条边简单路径当且仅当它们所属同一个极大白色连通块。

一张边子图根据极大白色连通块和黑色点给出了对原图点集 U 的划分 U=P1P2...PmQ1Q2...QkPi 对应极大白色连通块,Qi 对应一个大小大于 1 的边双。

那么 ci=2 的限制相当于说不能出现某个 Pi 满足存在限制 (sj,tj,2)sj,tjPi。假设一张边子图给出的对 U 的划分确定,可以据此判断其是否合法。

假设划分确定,某个 Pi 内部的连边数相当于这个点集导出子图的生成树计数,直接使用矩阵树定理计算是 Θ(2nn3) 的,其实也可以 Θ(2nn2) 不过不重要。某个 Qi 内部的连边数即数边双连通子图,可以 Θ(2nn3) 全部计算出。

之间的连边还是把一个 Pi,Qi 缩成一个点之后相当于做生成树计数。但注意因为要求 Pi 是极大的,不能将两个极大白色连通块相连!

回忆经典题 “n 种颜色的小球第 i 种有 ai 个,有多少种排列小球的方式使得没有同色小球相邻” 是如何解决的:容斥枚举一些小球对同色且相邻。这两个问题非常类似,因此处理这一限制也可以考虑容斥。

把连边看作两个阶段:第一阶段只能在 Pi 间连边,连边边权为 1,第二阶段可以任意连边,连边边权为 1

那么对于连出来边集一致(忽略边权)的一些生成树,假设其将两个极大白色连通块相连,这条边既可以在第一阶段连也可以在第二阶段连,因此权重抵消了。

于是设 fS 表示 S 导出子图生成树计数,fS=fSvalid(S)valid(S) 表示 S 是否能作为一个极大白色连通块,gS 表示 S 导出子图的边双连通边子图数量。设 transfer(F,c) 为将 F 进行每额外选一条割边贡献乘上 c 的正向 “边双连通-连通 变换” 后得到的集合幂级数。原问题的答案是 transfer(transfer(f,1)+g,1)U


原问题未必要求选出的边子图连通,注意到 transfer(transfer(f,1)+g,1) 相当于对所有 SU 计算了 S 导出子图中有多少连通边子图满足所有 (sj,tj,2) 的限制,只要 sj,tjS。原图任意的边子图根据连通块给出了对 U 的点集划分,一些划分出来的点集可能不满足连通性限制,对所有满足连通性限制的点集的答案做 exp 即可。

时间复杂度 Θ(2nn3)。更劣的 Θ(3nn) 在此数据范围下无法区分,也可通过。


如果有疑惑,更详细的分析以及一些背景知识介绍见 apio2025 我的讲课。

百里马拉松

idea, solution, std, data by _LHF_

本题标算为 O(nlognloglogn),然而出题人因为水平问题无法区分该做法和 O(nlogn) 的做法,出题人在此谢罪。

建议先阅读论文《浅谈树上邻域问题的一种基于长链剖分的解法》。

考虑对树进行长链剖分,

首先对于一个询问 (x,d),如果 x 的高度 d,那么 (fax,d)(x,d) 结果相同,此时不妨令 xfax,不断这么做直到不能这么做位置,该过程可以用倍增做到 O(logn)

简单转化一下,相当于是每条长链都挂了一条额外链,然后只需要处理所有挂在这个长链上的询问。

对于处理该长链子树外部贡献的方法,详见我的论文。

找到 (x,d) 左侧和右侧第一个碰到的点,然后考虑将询问拆成三个部分,中间那部分直接二区间合并分治即可,这样可以做到三次合并解决。

然后可以类似我在营员交流中提到的技巧,改成一次合并,总复杂度仍然是 nlogn,不过常数过大,所以无法接受。

事实上我们可以将该问题转化为一个树上祖先后代链查询的问题,具体来说,对于一条额外链,我们把每个位置都看成一个点,然后类似论文中“强制在线处理方法”连边,转化成树上链查询问题,用树上二区间合并分治即可。

实际上还能做得更好,考虑倍增分块,对于长度为 len 的额外链,找到最小的 b 满足 Bblen,然后将该额外链的长度扩充到 Bb。这样本质不同的额外链长度数量就不超过 logBn 条了,可以直接暴力枚举跳到了哪一个长度上,标算实现是 O(n(2B+logBn+C)),其中 C 是一个和 n,B 无关的常数。

然后我们简单处理一下即可,B=2 时复杂度为 O(nlogn)

注意到 B 不一定要取到 2,当 B 取到 (logn)eps 时理论复杂度为 O(nlognloglogn)。然而该做法常数较大,所以出题人几乎无法区分该做法和 O(nlogn) 的做法。

如果有人有更优的做法,欢迎和出题人联系。

评论

sofa
催催更
%sjy
> 建议先阅读论文《浅谈树上邻域问题的一种基于长链剖分的解法》 I tried searching for it on Google, but couldn’t find which it refers to. Could you please share the URL?
评论回复
zjy0001:你可以在这里找到它:https://github.com/enkerewpo/OI-Public-Library/blob/master/IOI中国国家候选队论文/国家集训队2025论文集.pdf
【该评论涉嫌黄赌毒内容,已被管理员隐藏】
评论回复
Hussein2024:【该评论涉嫌黄赌毒内容,已被管理员隐藏】
【该评论疑似为无意义的乱码,已被管理员隐藏】
我是傻逼!
1ัััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััั2ัััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััััั3ััััััััััััั
![超人熊](http://img.uoj.ac/utility/bear-flying.gif)
@
%sjy %shenjiyu %
评论回复
Hussein2024:此人的用户名骂 UOJ 可把这个人 ban 了……

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。