Codeforces1556F-概率状压DP

传送门

题意:

有$n$个队伍,每个队伍都有一个能力值$a_i$,每个两个队伍之间会打一场比赛,$i$打$j$胜利的概率为$\frac {a_i} {a_i+a_j}$,求能够击败所有队伍的数量的期望(如果a击败了b,b击败了c,可以视为a击败了c)。

$n\leq 14$

阅读更多

2021牛客多校第一场I Increasing Subsequence-期望DP

传送门

题意:

一个长为$n$的排列,有两个人轮流从中取数,每一轮中所取的数需要满足如下规则:

  1. 取的数大于之前所有人取的数
  2. 取的数的下标大于取数人之前取的数的下标
  3. 如果有多种取数方案,则随机进行取数
  4. 第一个人第一次取数随机
  5. 如果有人没法再取数,游戏结束

求最后期望能取数多少次。

阅读更多

BZOJ2142 礼物-扩展lucas

传送门

题意:

给定n及m个数a[1…m],再给定一个模数P,求$\sum_{i=1}^nC_{n-\sum_{j=1}^{i-1}a_j}^{a_i}$对P取模

($1≤n≤10_9,1≤m≤5$,设$ P=p_1^{c_1}\times p_2^{c_2}\times p_3^{c_3}\times …\times p_t^{c_t} $,$p_i$为质数,$1≤p_i^{c_i}≤10^5$)

阅读更多

BZOJ2957 楼房重建-线段树维护单调栈

题意:

​ 小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。
为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置,第i栋楼房可以用一条连接$(i,0)$和$(i,H_i)$的线段表示,其中$H_i$为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时,所有楼房都还没有开始建造,它们的高度均为0。在第i天,建筑队将会将横坐标为$X_i$的房屋的高度变为在在$Y_i$(高度可以比原来大—修建,也可以比原来小—拆除,甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

阅读更多

hdu6068 Classic Quotation-哈希

传送门

题意:

给定一个长度为$n$的串$s$,一个长度为$m$的串$t$。
有k次询问,每次给定$l,r$,在$[1,l]$中随机一个整数$i$,在$[r,n]$中随机一个整数$j$,问$t$在$s[1…i]+s[j…n]$中的出现次数。
$n,k\leq100000,m\leq100$

阅读更多