概率，$dp$。

设$dp[i][j]$表示有$i$个人在排队，$Tomato$排在第$j$个的情况下，到达目标状态的概率。$dp[n][m]$为答案。

当$j=1$时，$dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4$；

当$2<=j<=k$时，$dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4$；

当$k<j<=i$时，$dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]$。

将上面三个式子第一项往左移，左右同除以左边系数之后，得到：

当$j=1$时，$dp[i][1]=A*dp[i][i]+C$；

当$2<=j<=k$时，$dp[i][j]=A*dp[i][j-1]+B*dp[i-1][j-1]+C$；

当$k<j<=i$时，$dp[i][j]=A*dp[i][j-1]+B*dp[i-1][j-1]$。

其中$A=p2/(1-p1)$，$B=p3/(1-p1)$，$C=p4/(1-p1)$。

加下来就是要把这个东西算出来。又是一顿骚操作。

再写的简单一点吧：

当$j=1$时，$dp[i][1]=A*dp[i][i]+x[j]$，此时$x[j]=C$；

当$2<=j<=k$时，$dp[i][j]=A*dp[i][j-1]+x[j]$，此时$x[j]=B*dp[i-1][j-1]+C$；

当$k<j<=i$时，$dp[i][j]=A*dp[i][j-1]+x[j]$，此时$x[j]=B*dp[i-1][j-1]$；

$x[j]$可以通过$dp[i-1][....]$直接算出来。

假设现在我们需要计算$dp[4][1]$至$dp[4][4]$，我们分别设$dp[4][1]$至$dp[4][4]$为$a$,$b$,$c$,$d$。

得到四个等式：

$a=A*d+x[1]$ ①

$b=A*a+x[2]$ ②

$c=A*b+x[3]$ ③

$d=A*c+x[4]$ ④

将②代入③，再将新得到的③代入④，再将新得到的④代入①，

得到：$a=A^4*a+A^3*x[2]+A^2*x[3]+A^1*x[4]+A^0*x[1]$ ⑤，就可以求出$a$了，即求出了$dp[4][1]$。

⑤式子的得到是有规律的，自己写一遍就知道了。得到了$dp[4][1]$就可以知道$dp[4][2..4]$了。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include