首先设\(m\)为随从个数，\(k\)为暗影打击装甲的个数，\(p\)为剩余生命值，\(n\)为生命上限

然后考虑每个回合受到伤害，设\(A_i\)为每个回合被攻击\(i\)次的概率

\[ A_i=C^{i}_{k}*（\frac{1}{m+1}）^i*(\frac{m}{m+1})^{k-i}\\ \]

然后考虑答案，我们设\(F_i\)为当前有\(i\)滴血被干掉的期望回合数，再设\(g_i\)为当前回合打出超过\(i\)滴血的概率，容易得出

\[ F_i=\frac{1}{m+1}(g_{i+1}+\sum_{j=0}^{i}A_{j}(F_{i+1-j}-1))+\frac{m}{m+1}(g_i+\sum_{j=0}^{i-1}A_j(F_{i-j}+1))\\ F_i=\frac{1}{m+1}(1+\sum_{j=0}^{i}A_{j}F_{i+1-j})+\frac{m}{m+1}(1+\sum_{j=0}^{i-1}A_jF_{i-j})\\ \]

好像没有什么问题，但是还得考虑满血的情况，这个时候是回不上血的

所以最后得出来

\[ i!=n:\\ F_i=\frac{1}{m+1}(1+\sum_{j=0}^{i}A_{j}F_{i+1-j})+\frac{m}{m+1}(1+\sum_{j=0}^{i-1}A_jF_{i-j})\\ i==n:\\ F_n=1+\sum_{j=0}^{n-1}A_jF_{n-j} \]

然后考虑概率期望的通常做法：高斯消元

由于\(n=1500\)，高斯消元显然会TLE

然后我们观察一下这个方程组，发现第\(i\)个方程只有前\(i+1\)个系数不为\(0\)，所以考虑每次消元都只留下\(i,i+1\)，然后最后一个方程只有第\(n\)个位置上系数不为\(0\)，然后解出\(F_n\)，递推出答案就好了，那么复杂度就可以优化到\(O(n^2)\)了

提示：bzoj太慢，mod太多会TLE，请优化

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include