0310 模拟赛记录
\(\text{div1 }100+90+20=210\)。
题解
\(\text{difficulty}=2.5,3\)。
\(\text{tags}=线段树\)。
实际上倒数没有意义，首先令 \(a_i\leftarrow \frac{1}{a_i}\) 即可。
那么实际上需要维护区间平方、区间求和并对 \(998244353\) 取模。通过打表可以发现每个数经过若干次平方后形如 \(\rho\)，并且循环节为 \(24\) 的约数，且未进入循环节部分的长度不超过 \(24\)。
那么我们只需要维护每个数是否已经进入循环，以及是循环的第几个位置即可。在线段树的每个节点维护一个大小为 \(24\) 的数组表示再操作 \(0\sim 23\) 次后区间的和（\(24\) 次与 \(0\) 次相同），当区间内存在没有进入循环的数时使用势能均摊，而全部进入循环后就维护上面那个大小为 \(24\) 的数组，如果区间内存在修改就暴力重构。
修改时只需要找到当前是区间内循环的第几个位置即可得到新的区间和。查询与普通线段树相同。
注意当区间内存在没有进入循环的数时需要注意只能在区间内存在修改时暴力重构数组，否则可能导致在势能均摊时每次 \(\text{push_up}\) 多 \(24\) 的常数，复杂度可能被卡为 \(\mathcal{O}(n\log n\times 24^2)\)。
总时间复杂度 \(\mathcal{O}(24(n+q)\log n)\)。
\(\text{difficulty}=4,2.5\)。
\(\text{tags}=概率期望,动态规划\)。
观察题目发现当剩余 \(k\) 张卡时两个人都一定会抽取 \(\min(k,m)\) 张。
注意到两个人的决策类似 \(\text{min-max}\) 对抗搜索，考虑使用 \(\text{dp}\) 的形式，设 \(f_{0,s}\) 表示轮到第一个人操作，剩余集合 \(s\) 的元素，第一个人能够得到的最大权值的期望，\(f_{1,s}\) 表示轮到第二个人操作，剩余集合 \(s\) 的元素，能够使得第一个人得到的最小权值的期望。
那么我们暴力枚举能够抽取出卡的所有情况，可以得到（其中需要满足 \(|t|=\min(|s|,m)\)）
\[f_{0,s}=\frac{1}{p}\left(\sum_{t\subsetneqq s,t\not=\phi}\max(\max_{i\in t} (w_i+f_{1,s-\{i\}}),f_{1,s})\right)\\ f_{1,s}=\frac{1}{p}\left(\sum_{t\subsetneqq s,t\not=\phi}\min(\min_{i\in t} (w_i+f_{0,s-\{i\}}),f_{0,s})\right) \]注意到里面有 \(\max\) 的式子，无法直接计算，那么考虑从小到大考虑 \(s\)，每次枚举 \(f_{0,s}\) 然后带入第二个式子得到 \(f_{1,s}\)，再带回第一个式子得到 \(f_{0,s}\)，若与枚举的值相同则找到了 \(f_{0,s}\) 的正确取值。那么猜测这个过程可以二分，发现能过大样例。
直接做时间复杂度为 \(\mathcal{O}(3^n\log w\times n)\)，无法通过。
注意到实际上第一个人取出卡必然只会拿走最大的一个，而第二个人取出卡必然只会拿走最小的一个，所以可以对每个集合预处理出其权值最大最小值的位置，那么 \(i\) 必然只能取到这两种值，可以将复杂度中的 \(n\) 卡掉，将为 \(\mathcal{O}(3^n\log w)\)。
接下来考虑由于我们对 \(|t|\) 的限制较强，可以对每个 \(s\) 预处理出合法的 \(t\)，优化效果较为显著，可以通过。
\(\text{difficulty}=5,2\)。
\(\text{tags}=组合计数,\text{Cayley}定理\)。
首先考虑特殊性质 \(BD\)。实际上是将图划分为两部分，那么实际上要求连出来树后两部分是对称的。
那么显然我们只有一条跨过两部分的边，其余的必然是一部分内部的。那么考虑 \(\text{prufer}\) 序列求出其中一部分内部的边，然后加上最后一条跨过两部分的边。令 \(m=\frac{n}{2}\)，容易得到方案数为
\[2^{m-1}\times m^{m-2}\times m=(2m)^{m-1} \]其中乘的 \(2^{m-1}\) 表示每条边有两种方案，即连接两个大小为 \(2\) 的置换环有两种方案。
接下来考虑性质 \(D\)。实际上有一个非常经典的套路是我们考虑令 \(i\) 向 \(p_i\) 连边，那么可以得到若干个置换环。那么特殊性质 \(BD\) 实际上保证了每个置换环均为二元环。考虑扩展到特殊性质 \(D\)，实际上是若干个二元环和若干个单点。
进一步观察，我们发现一个二元环的树簇最多只能连接一个单点，因为如果连接了至少两个单点则必然产生一个包含这两个单点的环。
那么我们考虑先将单点连成一棵树，然后考虑将二元环树簇连上去。
我们设有 \(t_1\) 个单点与 \(t_2\) 个二元环。单点连成一棵树可以直接使用 \(\text{prufer}\) 序列。那么我们实际上需要将二元环划分为 \(k\) 个定根的联通块，然后将每个根挂在任意一个单点上。
实际上我们需要计算由 \(t_2\) 个点的联通块个数为 \(k\) 的生成森林个数（有根），由扩展 \(\text{Cayley}\) 定理得到方案数为 \(kt_2^{t_2-k-1}\)。
接下来考虑原问题，实际上是置换环的大小可能超过 \(2\)。
\(\text{Lemma 1}\)：一条树边连接的两个大小为 \(i,j\) 的置换环必然满足 \(i|j\) 或 \(j|i\)。
\(\text{Proof 1}\)：首先如果 \(\gcd(i,j)\not=1\)，我们可以直接考虑将 \(i,j\) 同时除掉 \(\gcd(i,j)\)。那么若 \(i\not=1\) 且 \(j\not=1\)，连接任意一条边必然导致左边 \(i\) 个点与右边 \(j\) 个点中任意两点都有连边，显然出环。
\(\text{Lemma 2}\)：置换环大小 \(\ge 3\) 时，其内部必然不存在树边。
\(\text{Proof 2}\)：考虑分类讨论。
- 如果两个点在环上的距离 \(d\) 不为环大小 \(k\) 的一半，则必然形成 \(\gcd(d,k)\) 个大小为 \(\frac{k}{\gcd(d,k)}\) 的环，不合法。
- 如果两个点在环上的距离 \(d\) 不为环大小 \(k\) 的一半，则必然形成 \(\frac{k}{2}\) 个二元环。显然这些二元环内部不可能连通，那么考虑其与外界连接的情况。若存在一个环的大小为 \(x(x|k,x<k)\)，那么必然成环；若存在一个环的大小为 \(x(x|k,x\ge k)\)，那么必然依然不连通，故不合法。
综上，得证。
\(\text{Lemma 3}\)：若 \(t_1=t_2=0\)，答案为 \(0\)。
\(\text{Proof 3}\)：由于仅有大小为 \(2\) 的置换环内部存在树边，设有两个置换环的大小 \(i,j\) 满足 \(i|j\)，那么连接这两个置换环后必然形成了 \(i\) 个联通块。容易发现如果没有大小为 \(1,2\) 的置换环则我们永远不能合并这 \(i\) 个联通块。
那么我们考虑从小到大依次拼上每个大小的环，答案即为所有大小环的方案数相乘。
我们考虑拼上大小为 \(i\) 的环，选一部分和前面的环连边。与上面二元环类似，选定一些点为根，可以得到
\[\sum_{j=1}^{t_i} \binom{t_i}{j}(jt_i^{t_i-j-1})i^{t_i-j}\left(\sum_{d|i,d<i}dt_d\right)^j \]前面的组合数为选定 \(j\) 个点作为根，使用扩展 \(\text{Cayley}\) 定理求出将 \(t_i\) 个点分成 \(j\) 个带根联通块，每两个联通的块有 \(i\) 的贡献，可以连在环大小比 \(i\) 小的环中的点上。
接下来我们考虑对 \(t_1\) 分类。
- \(t_1=0\)，此时需要将 \(t_2\) 提前加入并连成树，与上面特殊性质 \(BD\) 相同。
- \(t_i\not=0\)，直接使用 \(\text{prufer}\) 序列连成树即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
\(\text{difficulty}=0.5,0\)。
\(\text{tags}=-\)。
经过观察发现仅有在 \(3\) 个串相同时才有贡献，否则 \(f(s_i,s_j),f(s_j,s_k),f(s_k,s_i)\) 中至少有一项为 \(0\)。
直接拿 \(\text{unordered_map}\) 维护一下即可，时间复杂度 \(\mathcal{O}(n+|S|)\)。
总结
B 实际上应该尝试优化。一个简单的性质没有找到导致复杂度多一个 \(n\) 被卡掉。
C 的性质 \(BC,BD\) 实际上并不困难，有机会做出来。
标签：24,单点,记录,text,复杂度,大小,考虑,0310,模拟 From： https://www.cnblogs.com/fzj2007/p/17204875.html