AGC020F - Arcs on a Circle
太妙了。
题意
你有一个周长为$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左边）：
- $p_1+l_i\ge p_2+1$，也就是只考虑整数部分的区间$[x,y)$时相交。
- $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)$