Diary - 2024.12.24

今天摆完了有点。

待补：

• Solution - Luogu P11398 众数
• Solution - Luogu P11401 [Code+#8 初赛] 普勒亚
• Solution - Codeforces 2041K Trophic Balance Species
• Luogu P11408 [RMI 2020] 树咖 / Arboras 代码
• 想想 Luogu P11417 [Sloi 2024]D1T1 精卫 的线性（？），而且还有代码
• 整理一下 Luogu P11420 [清华集训 2024] 乘积的期望 然后尝试写一下

前两个题解被叉掉的原因单纯是我真的不太想写了，，，
有一种，额，确实是摆了，相对来说没有写了题解的题好吧，

题解可以看 Diary - 2024.12.20，额应该是吧。

Luogu P11408 [RMI 2020] 树咖 / Arboras

注意到有题解了且题解好像说得很简单，我是不是有问题？
虽然但是，我昨天回宿舍意识到了，这个贡献可以拆分为 \(dep\) 的减法，就只用关心 \(\max\)，写着应该会好写很多！

Luogu P11417 [Sloi 2024]D1T1 精卫。

我是数论低手，所以基本又是抄了题解，，，

考虑到 \(f\) 是个积性函数，所以依然是考虑从 \(g(x)\) 推出 \(g(x\times p^c)(p\nmid x)\)。

那么 \(g(x\times p^c) = \prod\limits_{i | x\times p^c} f(i) = \prod\limits_{i | x}\prod\limits_{j | p^c} f(i)f(j) = \prod\limits_{i | x} f(i)^{c + 1}\prod\limits_{j | p^c} f(j)^{\sigma_0(x)} = g(x)^{c + 1}g(p^c)^{\sigma_0(x)}\)。

考虑这个是 \(p^c\) 的合并，于是可以筛出来质数后直接 dfs 搜，具体来说就是直接按质数顺序 dfs，决定当前的次幂。
但这样子有点劣，因为统计贡献要到最后才能统计，所以可以直接往后枚举质数，并且开始枚举就代表钦定这个质数要被选。
这样就可以在碰到一个数的时候直接算贡献了，是吧。
但是这个 \(\sigma_0(x)\) 的次幂似乎需要光速幂呢，数论低手不会分析复杂度了。

但是注意到这个空间只有 50MB。
唯一一篇题解给出的做法是根号分治，先把只有小的质数的跑出来，否则 \(> \sqrt{n}\) 的质数只有一个，枚举这个质数，再枚举剩下由其他质数乘出来的部分，然后拼起来就行了。

但是这样开头就需要埃氏筛了，就是 \(\mathcal{O}(n \ln \ln n)\) 的。

注意到题解评论说有线性，那是不是埃氏筛都用不了了，那是不是不能从只考虑质数的角度来思考？

Luogu P11420 [清华集训 2024] 乘积的期望

喜欢想 poly 做法？好似好似。

我怎么又是复读机？

居然是两个部分拼起来，有点神秘阿，我应该从部分分入手的来着，别去直接想了。

首先对于这个乘积的形式一个想法就是每个位置覆盖的数量可以表示为“第 \(i\) 个区间有没有覆盖到”，对所有区间求和。
然后就可以乘法时展开括号，那么就可以枚举到 \(i\) 时钦定此时算上贡献的是这个区间，那么这个区间就要覆盖到。

那么对于 \(m\le 16\) 的部分，对于每个区间其实就是长度不超过 \(m\) 的限制。
那么实际上只关心覆盖到的点的最左和最右的，因为这决定了区间长度。
于是就应当有一个 \(\mathcal{O}(2^mnm)\) 的做法？

否则来说，发现一定有 \(m > \frac{n}{3}\)。
那么就可以类似放隔板的想法，每相距 \(m\) 的位置不可能有共同覆盖其的区间，那么就可以对于位置 \(i, m + i, 2m + i\) 一起考虑，限制就是总共被覆盖次数为 \(c\)（因为 \(m > \frac{n}{3}\) 所以必定会覆盖到其中一个）。
且如果知道了每个位置覆盖次数就可以推出最后的方案（懂这个意思但这个还需要回去思考一下）。
于是就可以设 dp 是 \(f_{i, j, k}\) 代表考虑到 \(i\)，\(m + i, 2m + i\) 分别覆盖次数是 \(j, k\) 的数量，然后枚举下一次的 \(j', k'\) 转移。
那么就是 \(\mathcal{O}(nc^4)\) 的。

那么这个应当是关于 \(c\) 是个多项式的，所以可以拉插，就是 \(\mathcal{O}(n^6)\)。

全在瞎说，细节还得多想。

感觉每天作业的布置都是，看起来觉得随便做做就做完了阿！然后实际上晚自习做到红温了还没做完，乐。
我觉得我做的速度已经比较快了阿？？？？？？

班主任确实是在周一升旗仪式红温了。
然后差不多是在训人吧，但是她为什么觉得我们班的问题只有抄作业和考试作弊，，，
有没有可能是某些学生的道德品行呢？

然后到下午发现有些同学都在以班主任的一些言论开玩笑。
虽然我也觉得说的挺扯的，但是这样子是不是还是不太好，，，
而且问题是这东西烂完了，我现在听一下就流汗，班里全是这些，，，
幽默。

班上有同学，在晚自习大声谈论。
然后班长说不要讲了，还要骂人，然后开始跟个几岁小孩一样在那里叫，让你站你也不站，让你不要讲了你还骂得批大声，，，
我真的无语了，果然是 sb 特质，这个人就没多少时间是正常的。

班主任感觉好像还不知道这个人犯了这个错的样子。
其实我觉得可能知道，毕竟直接班会班长还说过这个问题，结果她是笑一下。

哦哦牛皮，这么宽容的。

其实这么宽容也不是说不过去，毕竟我们这个班型是我不知道什么人想出来的开创出来的神人班型，喜欢做实验？
算了不能乱骂人，，，感恩感恩。
只能说学校的班型一届比一届看起来大胆，最先开始实验可能就是从我们班（？）。
难道我们班呈现出来的效果很好吗，，，

受不了了，感觉班风真不如正常实验班来着。
你们有这样的 sb 同学吗？你们有这样的 sb 同学吗？你们有这样的 sb 同学吗？

感觉待在班上一天比一天破防，额额，正常上个课都不行，，，