做题记录 26.1.13

szt100309 · 2026-01-13 08:55:57 · 个人记录

\textcolor{black}\odot P9041 [PA 2021] Fiolki 2

考虑 \text{LGV} 引理，每条边赋随机权值，令 e_{i,j}\;(k+1\le i\le n,1\le j\le k) 表示 j 到 i 的所有路径权值积之和，则 f(l,r)=\text{rank}(e_{l\sim r})，错误率不超过 O(\frac 1P)，其中 P 为模数

扫描 r，维护 e_{k+1\sim r} 的前缀线性基，容易得到 x=0\sim k 时最小的 l 从而统计答案

时间复杂度 O(mk+nk^2)

代码

参考

令 A(i,j) 表示 i 在 j 时刻活着，D(i,j) 表示已经死亡

则 A(i,j)\to A(i,j-1)，D(i,j)\to D(i,j+1)

对于第一种 (t,u,v) 连 D(u,t)\to D(v,t+1),A(v,t+1)\to A(u,t)

对于第二种 (t,u,v) 连 A(u,t)\to D(v,t),A(v,t)\to D(u,t)

显然有用的点只有 O(n+m) 个

求出每个 A(u,t+1) 可达的 D(\ast,t+1)，不可达的部分计入答案，注意特判必死的点

使用 bitset 可以做到时间复杂度 O((n+m)\log m+\frac {(n+m)n}\omega)

每次选择 B 个点一起处理，可以做到空间复杂度 O(\frac{(n+m)S}\omega)，建议取 B=10^4 级别

代码

参考

不妨先将边权归到 [0,1]，则答案为

\sum_{\varnothing\subset S\subset [1,n]} \left(\frac12\right)^{|S|(n-|S|)} \prod_{u\in S,v\notin S} 2w(u,v)

考虑对于每个 |S| 求出 \sum_S \prod_{u\in S,v\notin S} 2w(u,v)，则可以统计答案

暴力实现为 \~O(2^n) 的，发现只需要对于每个给出边的连通块计算 \sum_S \prod_{u\in S,v\notin S} 2w(u,v) 之后卷积即可

时间复杂度 O(n^3+m^22^m)

代码

参考

显然大小为 n 的竞赛图的哈密顿回路数量之和为 (n-1)! 2^{\binom n2-n}（(n-1)! 种选择回路的方式，剩下 \binom n2-n 条边可以存在或不存在），因此考虑如何计算大小为 n 的强连通竞赛图数量

令数量为 f_n，易得

f_n=2^{\binom n2} - \sum_{1\le i<n} f_i 2^{\binom{n-i}2} \binom ni

其中枚举 i 个点为子 \text{SCC}，剩余 n-i 个点之间任意，两者之间的边都从后者指向前者

令 g_i=2^{\binom i2}，F,G 分别为 f,g 的 \text{EGF}，则 F=G-F\times G，F=\frac{G}{G+1}，容易 O(n\log n) 求出 f_{1\sim n}

代码