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

[传送门][https://ac.nowcoder.com/acm/contest/11166/I]

题意:

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

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

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

阅读更多

Codeforces908D New Year andArbitrary Arrangement-dp

传送门

题意:

给出$k,p_1,p_2$,一开始串为空,每次有$\frac {p_1}{p_1+p_2}$的概率在串中加一个a,$\frac {p_2}{p_1+p_2}$的概率在串中加一个b,当串中有k个为ab的子序列停止加字符,求停止加字符后串中为ab的子序列的个数的期望,假设结果为最简分数$\frac{ans_1}{ans_2}$,输出$ans_1\times ans_2^{-1}\mod(1e9+7)$。

阅读更多