[CodeForces908D] New Year and Arbitrary Arrangement

题目链接

期望dp_CF908D

题解

我们用\(dp[i][j]\)表示前缀包含\(i\)个\(a\),\(j\)个\(ab\)子串的所有字符串,得到的期望\(ab\)子串的个数.

如何转移?

在这个前缀后面加上一个\(a\):\(dp[i][j]+=dp[i+1][j] \times \frac{P_a}{P_a+P_b}\)

概率就是\(\frac{P_a}{P_a+P_b}\)

在这个前缀后面加上一个\(b\):\(dp[i][j]+=dp[i][i+j] \times \frac{P_b}{P_a+P_b}\)

概率是\(\frac{P_b}{P_a+P_b}\)

边界?

答案是\(dp[1][0]\)

边界是什么?

边界不止可能是固定的\(j\),还需要包含一些例如前缀无穷多个\(a\)的情况,因为一旦出现一个\(b\)就会使一般的递推循环\(i\)增加到无穷大.(转移方程加一个\(b\)直接加到\(i+j\))


数学过程计算出初始状态

令\(P_a=\frac {P_a}{P_a+P_b}\),\(P_b=\frac {P_b}{P_a+P_b}\),\(S=dp[i][j]\)

列出式子:

\[S=(i+j)P_b+P_a(i+j+1)P_b+P_a^2(i+j+2)P_b+……\]

左右同乘一个\(P_a\):

\[P_aS=P_a(i+j)P_b+P_a^2(i+j+1)P_b+……\]

错位相减:

\[S-P_aS=(i+j)P_b+(P_a+P_a^2+P_a^3+……)P_b\]

等比数列:

\[(1-P_a)=(i+j)P_b+\frac{P_a(1-P_a^\infty)P_b}{1-P_a}\]

因为\(lim_{x\to\infty}P_a^x\)无限接近与0,所以看作0.

极限是这样理解的吧QAQ,有错误求dalao指出

\(1-P_a\)不就是\(\frac{P_a+P_b}{P_a+P_b}\ -\ \frac{P_a}{P_a+P_b}\)

化简一下不就是\(\frac{P_b}{P_a+P_b}\)不就是现在的\(P_b\)

带入

\[P_bS=(i+j)P_b+\frac{P_a+P_b}{P_b}\]

最后把\(p_b\)除到右边去.

\[S=i+j+\frac{P_a}{P_b}\]

得到初始状态

\[dp[i][j]=i+j+\frac{P_a}{P_b}\]


然后我们要记得及时取模,所以\(\frac{P_a}{P_b}\)如何取模又恶心到了.

求一下\(P_b\)的逆元就好了.

也就是\(ksm(P_b,mod-2)\)


最后一发记忆化搜索避免无脑循环边界.


By:Wahacer

2018.1.3

15:51

发表评论

电子邮件地址不会被公开。 必填项已用*标注