apio2024 d1

agc060E

考虑刻画拓扑序。

计数，计 \(2^n\) 个点的树的所有拓扑序中满足条件的树的个数。

设 \(f_n\) 为：\(n\) 层的满二叉树的拓扑序树，这可以通过递推得到。现在只看根到 \(A\) 与 \(B\) 的两条链，一边处理这两条链，一边插入其他子树。

当放入某条链的第 \(i\) 个节点时，可以同时把它的那棵不重要的子树插进去。于是有 dp：\(f_{i, j}\)：左链已经放了 \(i\) 个点，右链已经放了 \(j\) 个点，方案数。

CF1096E

所求的是 \(P(a_1\text{is winner} | a_1 \geq r)\)，因为 \(P(a_1 \text{is winner})=1/n\)，我们求 \(P(\max a_i \geq r)\) 后乘 \(1/n\) 即可。

（晚点应该补一个贝叶斯公式的解释）

后者二项式反演即可。

钦定 \(i\) 个位置 \(\geq r\)，则贡献为 \(\displaystyle \sum (-1)^{i} \binom{s-ir+p-1}{p-1}\)，最后乘上 \(\dfrac{1}{n \binom{s-r+p-1}{p-1}}\)。复杂度 \(O(s+p)\)。