可以手推一下,
每次开宝箱得到滚木概率都是\frac1nn1,第i次开宝箱得到和之前得到的一样的卡牌概率为\frac{i-1}nni−1
所以递推,设第i次开宝箱就可以得到滚木的概率是f_ifi得到转移式f_i=(1-\sum_{j=1}^{i-1}f_j)*\frac infi=(1−∑j=1i−1fj)∗ni
ans=\sum_{i=1}^nf_i*ians=∑i=1nfi∗i,O(n)即可
**2.跑步--solution**- 令f_xfx表示从起点到点x的最短距离,如果x不能被到达,令f_x=\inftyfx=∞
- 我们称点x可以从点y转移过来当且仅当f_x=f_y+1fx=fy+1且点x和点y相邻
- 称一条路径是合法的当且仅当这条路径是一个至少包着一颗树的环,且经过起点。
进入正题:
描述一个状态:
这个圆表示一条合法路径,其中有4个点,满足点pp是路径中f_xfx最大的一个点。p_左p左和p_右p右表示两个紧挨着的p的路径上的点。点v表示这条路径上和点p相邻但不能转移到p的点。
-
证明描述的这个状态存在
因为这是一个路径,所以点pp一定可以从点p_左p左和点p_右p右转移过来。此时p_左p左和p_右p右一定不相邻否则这就不是最优路径,所以一定存在点v且v不能转移到p。
-
证明描述的这个状态一定表示一条合法路径
当存在点v时,一定是因为这条路径包含了至少一颗树,否者点v可以转移到点p。
所以这个状态表示的路径一定合法。
-
证明一条最优合法路径一定可以找到这样4个满足条件的点
一条最优合法路径中一定存在距离起点最远的点,所以存在点p,p_左p左和p_右p右
因为这条路径包含至少一棵树,所以存在v点使得v不能转移到p
-
结论
存在上述的4个满足条件的点时,一定存在这样一条合法路径。
-
实现
所以我们枚举点pp,再验证是否存在满足条件的点即可。
细节:在验证的时候因为路径上最大的点可以有两个,所以要讨论6种情况。
从大到小枚举 gcd,设为g,钦定 i,j 都是 g 的倍数,然后假定 gcd(i,j) 就是 g 做一次卷积。但这样会算到真正的 gcd 是 g 的倍数的情况,做一个简单的容斥减掉即可。
复杂度:O(n log^2 n),常数不大。
如果想要数据或标程可以去https://share.weiyun.com/5WxfkoNe
全部评论
(0) 回帖