11.19 联测

又是 Div2。

Div1 T1

数学题。

交点有 $nm+1$ 个。称第 $i$ 个圆上的点在第 $i$ 层上。

考虑第 $i$ 层上的点对 $j>i$ 层的贡献。

设答案的 $\pi$ 的系数为 $a$，有理数项为 $b$。

则 $a \larr 2(n-i)i(m-1)m+i(m-1)m$，$b \larr 4(n-i)im+2im+(n-i)(n-i+1)m$。

发现扇形的两边相加有可能小于弧长，全部错了，推倒重来。

设最后一次不满足上面的条件是两点相隔 $p$。

$a \larr 2(n-i)i(p+1)p+i(p+1)p$，$b \larr 4m(n-i)i(2m-2p-1)+2mi(2m-2p-1)+2(n-i)(n-i+1)m^2$。

Div2 T2

dfs 枚举断的其中一个点 $u$，考虑快速查找另一个点 $v$。

维护两个 multiset，表示 $u$ 的祖先的 $siz$ 集合，已经遍历过的且不是 $u$ 的祖先的 $siz$ 集合。

• $v$ 是 $u$ 的祖先。在 $s1$ 中查找 $\frac{n+siz_u}{2}$。
• $v$ 不是 $u$ 祖先。在 $s2$ 中查找 $\frac{n-siz_u}{2}$。

Div2 T1

显然两点间不能连边当且仅当已经有边或者不在一个点双内。

所以 $ans=\sum \frac{siz_i(siz_i-1)}{2}$。

Div1 T2

求有多少个长度为 $n$ 的排列 $\{a\}$，使得 $\forall a_i>k,\exist j<i,a_j\ge a_i-k$。

考虑在值域上对前缀最大值进行 dp。

发现前缀最大值的位置并不重要，因为它必须填在当前能填的最前面的位置。

$f_i \larr f_j\times A_{n-j-1}^{i-j-1}$，系数的意思是在 $j$ 后面选 $i-j-1$ 个位置给 $(j,i)$。

前缀和优化一下。

Div1 T3

设 $i$ 在 $P$ 中出现的位置为 $a_i$。

数一定是从大往小删的，反过来，看成从小到大填数。

设包含 $a_0,a_1,\dots,a_i$ 最小区间为 $[l,r]$。那么 $a_{i+1}\in[1,l) \cup (r,n]$ 中。

$m$ 个已经有的数把 $P$ 分成 $m+1$ 个”间隙“。

设 $f_{i,l,r}$ 表示当前填到第 $i$ 个数，能够往 $[1,l]$ 间隙的左侧放数，能往 $[r,m+1]$ 的右侧放数。

• $i+1$ 在 $A$ 中出现了。此时把 $l \larr \min(l,a_{i+1}),r \larr \max(r,a_{i+1}+1)$ 后转移。

• $i+1$ 没在 $A$ 中出现。此时枚举 $a_{i+1}$ 放在哪个位置转移。

直接做复杂度 $O(n^4)$，可以前缀和优化到 $O(n^3)$，但是好像能直接冲过去。

Div1 T4

$1$ 的位置不影响，不妨钦定 $p_1=1$，最后答案 $\times 2^n$。

考虑 $1$ 胜利的条件，设第 $i$ 组为 $p_{2^i+1},p_{2^i+2},\dots,p_{2^{i+1}}$。

$1$ 胜利当且仅当每组中的最小值不在 $A$ 中。

考虑容斥，$g(s)$ 表示钦定 $s$ 中的组的最小值在 $A$ 中的方案数。

考虑 dp，设 $f_{i,s}$ 表示当前考虑到 $A_i$，已经钦定的组为 $s$。

这样设状态有个精妙之处：$s$ 刚好是已经确定位置的人数。

将 $A$ 从大到小排序。

• 将第 $j$ 组的最小值钦定为 $A_{i+1}$，此时 $f_{i+1,s|2^j} \larr f_{i,s}\binom{2^n-s-A_{i+1}}{2^k-1}(2^k)!$。
• 不钦定任何一组，此时 $f_{i+1,s} \larr f_{i,s}$。

最后 $g(s)=f_{m,s}(2^n-s-1)!$。