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)$

# 概率

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×