第二十四次

· · 个人记录

寄不如人，肝败吓疯。

A

先考虑咋交换两个数，然后分别处理每个环。

B

设 s_u 表示 u 子树大小，则点 u 有 \dfrac 1{s_u} 概率被自己删去，

即点 u 有 \dfrac 1{s_u} 概率被选，即点 u 期望被选 \dfrac 1{s_u} 次，所以期望共选 \sum\limits_{i=1}^n\dfrac 1{s_i} 个点。

C

设 c_i=\sum\limits_{j=1}^n[a_j\ge i]-n+i 表示 i 可选的位置数，

则符合要求的排列共有 s=\prod\limits_{i=1}^nc_i 种，若 \exists c_i=0 显然答案为 0。

考虑每对位置 i,j|i<j 在多少排列中是逆序对。先考虑 a_i\le a_j 的情况。

此时 p_j<p_i\le a_i，于是令 a_j\gets a_i，发现此时 i,j 是逆序对与顺序对的方案数相等，且 \forall k\in(a_i,a_j],c_k 减少 1，

所以此时 i,j 在 \dfrac S2\prod\limits_{k=a_i+1}^{a_j}\dfrac{c_k-1}{c_k} 个排列中是逆序对。

考虑预处理 d_i=\prod\limits_{j=1}^i\dfrac{c_j-1}{c_j}，则 \dfrac S2\prod\limits_{k=a_i+1}^{a_j}\dfrac{c_k-1}{c_k}=\dfrac {Sd_{a_j}}{2d_{a_i}} 吗？

实际上并不是，考虑 \dfrac{c_k-1}{c_k}\ne 0，而 d_{a_i},d_{a_j} 中有 0 的情况。

改变 d_i 的定义为 d_i=\prod\limits_{j=1,c_j\ne 1}^i\dfrac{c_j-1}{c_j}，设 l_i 表示 i 前第一个 c_i=1 的位置，

考虑枚举 j，则 j 的贡献为 \dfrac S2\sum\limits_{i=l_{a_j}}^{a_j}\prod\limits_{k=i+1}^{a_j}\dfrac{c_k-1}{c_k}=\dfrac S2\sum\limits_{i=l_{a_j}}^{a_j}\dfrac{d_{a_j}}{d_i}，此时保证了 i\ge l_{a_j}，所以式子成立。

$a_i>a_j$ 倒着做一遍。 # D 考虑 $i$ 人仅当存在某人选择 $(a_i,b_i)$ 的位置时，可以选择 $b_i$，此时选法与排列唯一对应，问题变为统计符合条件的选法数。 设 $l_i$ 表示最小的 $j$ 使得 $b_j\ge a_i$，$r_i$ 表示最大的 $j$ 使得 $a_j\le b_i$，则 $i$ 人不符合条件时 $[l_i,r_i]$ 的人都可以确定选法， 于是两个 $[l,r]$ 有交集的人不可能同时不符合条件，则钦定 $S$ 中的人不符合条件，共有 $2^{n-\sum\limits_{i\in S}r_i-l_i+1}$ 种选法，答案即为 $\sum\limits_{S}(-1)^{|S|}2^{n-\sum\limits_{i\in S}r_i-l_i+1}$。 设 $f_i=\sum\limits_{\forall j\in S,[l_j,r_j]\in[1,i]}(-1)^{|S|}2^{n-\sum\limits_{i\in S}r_i-l_i+1}$，考虑加入 $r_j=i$ 的区间，则 $f_i=\sum\limits_{r_x=i}(\sum\limits_{j=0}^{l_x-1}-2^{-(r_x-l_x+1)}f_j)-2^{n-(r_x-l_x+1)}$。