AGC020F - Arcs on a Circle

太妙了。

link

题意

你有一个周长为\(c\)的圆，现在你要把\(n\)条弧放到圆上。

第\(i\)条弧的长度为\(l_i\)，半径和圆半径相等。

对于每条弧，在圆上随机一个点，然后作为这条弧的中点。

求圆上每个点都被至少一条弧覆盖的概率。

假设一条弧可以覆盖到端点。

\(2\le n\le 6,1\le l_i\lt c,2\le c\le 50\)，\(n,c,l_i\)都是整数。 ### 题解 考虑以最长的弧的左端点为\(0\)，右端点为\(l_i\)（假设最长的为第\(i\)条弧），然后你可以从0处断开然后把它拉直，由于其它弧左端点在\([0,c)\)时，右端点不可能\(\gt l_i+c\)，所以可以直接忽略超过\(c\)的部分，问题变成了覆盖线段。

设第\(i\)条弧的左端点为\(p_i+q_i\)，其中\(p_i\)是整数部分，\(q_i\)是小数部分。

两条弧相交有两种情况（假设1在2左边）：

1. \(p_1+l_i\ge p_2+1\)，也就是只考虑整数部分的区间\([x,y)\)时相交。
2. \(p_1+l_i=p_2\)，且\(q_1\ge q_2\)，也就是整数部分不相交，小数部分相交。

由于\(c,l_i\)是整数，\(q_1..q_n\)只有相对的大小关系有用。任意两个相等的概率都是0，所以考虑两两不同。

除了\(q_i=0\)以外，其它的相对大小关系每种概率相等，直接枚举大小关系的排列就可以了。

接着考虑整数部分。直接枚举整数部分显然会超时。考虑按照左端点升序填弧，状压dp+前缀和优化即可。

时间复杂度\(O((n-1)!2^{n-1}(nc)^2)\)