题面

有 NN 个玩家要激活某种游戏，然而游戏的激活服务器对于这 NN 个玩家的激活请求只能一个一个处理（初始时主角 Tomato 排在第 MM ）。

对于队列中的第一个人，激活时可能遇到一下四种情况：

  • 激活失败：队列不变，服务器将再次尝试激活当前玩家（概率 PactFailP_\text{actFail} ）；
  • 连接失败：当前玩家被扔至队尾（概率 PconnLostP_\text{connLost} ）；
  • 激活成功：当前玩家离开队列（概率 PactSuccessP_\text{actSuccess} ）；
  • 服务中断：服务器炸了，无符继续处理任何请求（概率 PdownP_\text{down} ）。

求服务器服务中断并且此时 Tomato 排名 ≤K\leq K 的概率（后文中记该事件为事件 AA ）。

数据范围：

1≤M≤N≤20001 \le M \le N \le 2000

题目链接

分析

我们用 dp[i][j]dp[i][j] 来表示队列长度为 ii 且 Tomato 排在第 jj 时事件 AA 发生的概率。那么很显然，我们所要求的就是 dp[N][M]dp[N][M] 。

如何进行状态转移？我们不难推出：

dp[i][j]={PactFaildp[i][1]+PconnLostdp[i][i]+Pdownj=1PactFaildp[i][j]+PconnLostdp[i][j−1]+PactSuccessdp[i−1][j−1]+Pdown2≤j≤kPactFaildp[i][j]+PconnLostdp[i][j−1]+PactSuccessdp[i−1][j−1]j>k dp[i][j] = \begin{cases} P_\text{actFail} dp[i][1] + P_\text{connLost} dp[i][i] + P_\text{down} & j =1 \\ P_\text{actFail} dp[i][j] + P_\text{connLost} dp[i][j - 1] + P_\text{actSuccess} dp[i - 1][j - 1] + P_\text{down} & 2 \le j \le k \\ P_\text{actFail} dp[i][j] + P_\text{connLost} dp[i][j - 1] + P_\text{actSuccess} dp[i - 1][j - 1] & j > k \\ \end{cases}

接下来我们对其进行化简：

dp[i][j]={PconnLostdp[i][i]+Pdown1−PactFailj=1PconnLostdp[i][j−1]+PactSuccessdp[i−1][j−1]+Pdown1−PactFail2≤j≤kPconnLostdp[i][j−1]+PactSuccessdp[i−1][j−1]1−PactFailj>k dp[i][j] = \begin{cases} \frac{P_\text{connLost}dp[i][i] + P_\text{down}}{1 - P_\text{actFail}} & j =1 \\ \frac{P_\text{connLost}dp[i][j - 1] + P_\text{actSuccess}dp[i - 1][j - 1] + P_\text{down}}{1 - P_\text{actFail}} & 2 \le j \le k \\ \frac{P_\text{connLost}dp[i][j - 1] + P_\text{actSuccess}dp[i - 1][j - 1]}{1 - P_\text{actFail}} & j > k \\ \end{cases}

为了方便，我们不妨记：

PconnLost′=PconnLost1−PactFailPactSuccess′=PactSuccess1−PactFailPdown′=Pdown1−PactFail \begin{aligned} P_\text{connLost}' & = \frac{P_\text{connLost}}{1 - P_\text{actFail}} \\ P_\text{actSuccess}' & = \frac{P_\text{actSuccess}}{1 - P_\text{actFail}} \\ P_\text{down}' & = \frac{P_\text{down}}{1 - P_\text{actFail}} \\ \end{aligned}

因此，转移方程被进一步化简为：

dp[i][j]={PconnLost′dp[i][i]+Pdown′j=1PconnLost′dp[i][j−1]+PactSuccess′dp[i−1][j−1]+Pdown′2≤j≤kPconnLost′dp[i][j−1]+PactSuccess′dp[i−1][j−1]j>k dp[i][j] = \begin{cases} P_\text{connLost}'dp[i][i] + P_\text{down}' & j =1 \\ P_\text{connLost}'dp[i][j - 1] + P_\text{actSuccess}'dp[i - 1][j - 1] + P_\text{down}' & 2 \le j \le k \\ P_\text{connLost}'dp[i][j - 1] + P_\text{actSuccess}'dp[i - 1][j - 1] & j > k \\ \end{cases}

好的，现在我们已经解决了转移方程的问题，接下来要考虑的是该怎么写代码咯。

观察转移方程，不难发现如果我们从 i=1→Ni = 1 \rightarrow N 进行递推的话，当我们在计算 dp[i]dp[i] 时 dp[i−1]dp[i - 1] 事实上全是常量。因此，方程中除了含 PconnLost′P_\text{connLost}' 的一项，剩余项均可看作常数项。

我们不妨将第 jj 个式子的常数项记作 c[j]c[j] ，因此在计算 dp[i]dp[i] 时相当于求解 ii 元一次方程组：

{dp[i][1]=PconnLost′dp[i][i]+c[1]dp[i][2]=PconnLost′dp[i][1]+c[2]...dp[i][i]=PconnLost′dp[i][i−1]+c[i] \begin{cases} dp[i][1] & = P_\text{connLost}'dp[i][i] + c[1] \\ dp[i][2] & = P_\text{connLost}'dp[i][1] + c[2] \\ ... \\ dp[i][i] & = P_\text{connLost}'dp[i][i - 1] + c[i] \\ \end{cases}

ii 元一次方程组小学生都会解……

dp[i][i]=PconnLost′dp[i][i−1]+c[i]=PconnLost′(PconnLost′dp[i][i−2]+c[i−1])+c[i]= ...=PconnLost′i−1dp[i][1]+PconnLost′i−2c[2]+...+PconnLostc[i−1]+c[i]=PconnLost′idp[i][i]+PconnLost′i−1c[1]+...+PconnLostc[i−1]+c[i] \begin{aligned} dp[i][i] & = P_\text{connLost}'dp[i][i - 1] + c[i] \\ & = P_\text{connLost}'(P_\text{connLost}'dp[i][i - 2] + c[i - 1]) + c[i] \\ & = \ ... \\ & = {P_\text{connLost}'}^{i - 1}dp[i][1] + {P_\text{connLost}'}^{i - 2}c[2] + ... + P_\text{connLost}c[i - 1] + c[i] \\ & = {P_\text{connLost}'}^{i}dp[i][i] + {P_\text{connLost}'}^{i - 1}c[1] + ... + P_\text{connLost}c[i - 1] + c[i] \\ \end{aligned}

化简，得：

dp[i][i]=∑j=1i(PconnLost′i−j⋅c[j])1−PconnLost′i dp[i][i] = \frac{\sum\limits_{j = 1}^{i}({P_\text{connLost}'}^{i - j} \cdot c[j])}{1 - {P_\text{connLost}'}^{i}}

然后剩下的变量只需要递推求解一下就行咯。

接下来我们剩下的唯一问题就是 c[j]c[j] 具体是什么了。我们也不难看出：

c[j]={Pdown′j=1PactSuccess′dp[i−1][j−1]+Pdown′2≤j≤kPactSuccess′dp[i−1][j−1]j>k c[j] = \begin{cases} P_\text{down}' & j = 1 \\ P_\text{actSuccess}'dp[i - 1][j - 1] + P_\text{down}' & 2 \le j \le k \\ P_\text{actSuccess}'dp[i - 1][j - 1] & j > k \end{cases}

最后要注意的是，如果 Pdown=0P_\text{down} = 0 ，那概率肯定是 00 啦，还算个毛线~

有了上述分析，我们就可以很容易地用递推写出代码了。

实现

像我这种智商欠费的🐷在写概率 DP 时还是不要为了省一点空间作死下标从 00 开始了…… 😭

完整参考代码

%%%