Day 1
报道日。前情提要：结束了 PKUWC，前往龙山书院参加 NOIWC。
今天没有安排讲课，选择了一些经典的题目完成。
[ABC387G] Prime Circuit
原题链接：https://atcoder.jp/contests/abc387/tasks/abc387_g
简要题意：对于 \(n\) 个点、有标号、每个环长度均为奇质数的仙人掌计数。
考虑 Prüfer 序列的相关结论：一个 \(n\) 个点 \(m\) 条边的有标号无向图有 \(k\) 个连通块，需要添加 \((k-1)\) 条边使得整个图连通，令每个连通块大小为 \(s_i\)，方案数为 \(n^{k-2}\cdot\prod\limits_{i=1}^k s_i\)。
结合一些有标号图的计数技巧：每次加入一个环，钦定结点 \(1\) 所在的环大小为 \(c(c=1\lor c\in\mathbb{P})\)（其中 \(\mathbb{P}\) 表示质数集）——令 \(f_i\) 为 \(i\) 个点时答案的系数和（即最终答案为 \(n^{-2}f_n\)），有转移 \(f_i=n\sum\limits_{c=1}^i[c=1\lor c\in\mathbb{P}]\cdot c\cdot\mathrm{C}_{i-1}^{c-1}\cdot\frac{(c-1)!}{2}\cdot f_{i-c}\)。暴力做时间复杂度为 \(O\left(\dfrac{n^2}{\ln n}\right)\)。
正解是多项式复合，但是考虑到 \(12\mathrm{s}\) 的时限，所以尝试直接做。将求和中的一些系数提到外面算，加法时使用 __int128 最后统一取模；实测可以在 \(11\mathrm{s}\) 内通过。
提交记录：Submission #61721116
[ABC282G] Similar Permutation
原题链接：https://atcoder.jp/contests/abc282/tasks/abc282_g
简要题意：长为 \(n\) 的排列 \(a\) 与 \(b\) 的相似度被定义为：满足 \((a_{i+1}-a_i)(b_{i+1}-b_i)>0(1\le i<n)\) 的 \(i\) 的数量。求有多少对 \(1\sim n\) 的排列相似度恰为 \(k\)，答案对 \(P\) 取模。
考虑 AtCoder DP 经典 26 题中 Permutation 的套路，令 \(f_{i,s,a,b}\) 为考虑了前 \(i\) 个位置，当前相似度为 \(s\)，第一个排列中填入的最后一个数在之前的数中排名为 \(a\)、第二个排列中填入的最后一个数在之前的数中排名为 \(b\) 的方案数；转移分四种情况讨论，暴力做时间复杂度是 \(O(n^5)\) 的、空间复杂度是 \(O(n^4)\) 的，无法通过；但是考虑到第一维可以滚动数组优化，而转移时可以使用二维前缀和优化，这样时间复杂度是 \(O(n^4)\) 的，空间复杂度是 \(O(n^3)\) 的。
提交记录：Submission #61751215
标签：mathbb,连通,个点,cdot,复杂度,实录,NOIWC2025,mathrm From： https://www.cnblogs.com/physics212303/p/18677693