总结

正月十三，不想说太多。

题解

同上，不想说太多。链接放在这里了：link

D240222A  Tree

送分题，对于一个有根树的每个点求有多少个集合满足这个集合内点的 LCA 是这个点。乱搞就能过，不细说了。

D240222B  Journey

以下是(相对)简要的描述：

给出一棵个点，以为根的有根树。点的父亲为，点有权值​，满足​ 且所有​ 构成一个到的排列。

小 A 会在这棵树上沿着最短路径从一个节点走到该节点子树内的一个节点。当小 A 经过点时，有​​ 的概率小 A 会得到一个数​。

记​ 表示小 A 从走到时，得到的所有数的最大公约数为的概率。给出​，定义：

这里认为零个数的最大公约数为，且。

最后，设的子树构成集合​，对于每个点求出，答案对取模。

这道题是的，恶心的卡常题，但是上限满分的只有分，因为良心的出题人意识到了这是错误的行为，其它最大的是的，时限，但是可惜的是我们可敬的教练啊，在分 subtask 的时候将两个的点给分到前一个去了哟。

这道题怎么说了，考场上写了个玄学做法，能过，可以理解为启发式合并，和正解思路也差不多。就是先给莫比乌斯反演一下，这个我觉得还是比较容易想到，然后我们枚举公因数。这里先不考虑 0 的情况，最后减去就完了，所以我们每个点最开始概率都是，枚举的时候相当于把关键点给改为。我们怎么操作呢？就是看它会增加多少，然后记到一个数组里，最后再像正常地从下往上递推，也就是每次乘上，最后每个点加上增加地就行。最后再减去 0 的情况。这里的操作可以不用建立虚树，因为造成贡献的只有关键点中的儿子，因此弄个栈，按照 dfs 序排好搞就可以了。做法很多。

卡常小技巧：vector 提前开好空间，或者不用，建图使用邻接表，使用快读和快写（这个输出量真大）。

D240222C  Festival

以下是(相对)简要的描述：

有一个个点组成的环，第条边连接。每个点有点亮和熄灭两种状态。初始所有点处于熄灭状态。

仪式开始后，在每个时刻，会依次发生如下两个事件：

1. 设当前为时刻，考虑每一个点，如果存在一个与相邻的点使得该点在时刻状态为点亮，则状态变为点亮。否则的状态不变。

2. 小 B 随机选择一个点，使用魔法将它的状态变为点亮。

   时刻从开始计算。称仪式的用时为最小的时刻，使得时刻后所有点状态都为点亮。求仪式用时的期望，答案对给定大质数取模。

是否能想起前天的 [[总结/2024年2月20日模拟赛#[B. zzzyyds](http //www.nfls.com.cn 10611/contest/1167/problem/2)|2024年2月20日模拟赛 T2]] 呢？没错，虽然正解不是那天的法二，但是我没看懂。而且根据题解，pb 用的就是那种，但是正解没有细说。而且正解是通过不正确的最后发现状态数很少才过的！表示气愤ヾ(≧へ≦)〃！但是他也有可能算错了复杂度，有一个可能是，因为今天早上魏老师就是不小心算错复杂度了，但是差点过了（不小心被卡常了）。

所以这里来讲讲的方法，邓老师已经成功优化到了，目前我还不会，薄纱 std。

就是还是容易发现不亮段的可重集和段数一样时，概率肯定时一样的。想到了这一点为什么我考场上没有切掉呢？是因为还有一个小技巧，这道题的转移不能像那道题一样每次全部的状态数都能算出来然后转移乘一个比例就完了，这道题要用到之前的一个小技巧：挖坑 dp 的思想！[[2023年12月15日总结]] 来自这一天的。可以考虑到每次转移是合并两个段而已，这样就方便很多了！似乎前天那道题也可以这样。说明还不是很熟悉挖坑 dp 啊 doge。然后这里之所以复杂度是这个的原因是容易发现环的个数不会超过个。

后记

不想记了哦。