定义每个操作的成功率为$p[i]$，注意$p[0]=p[n+1]=0$，后面会涉及这个边界

定义前缀积$prod$：

$$prod_n=\prod _{i=1}^n p_i$$

定义$f_{i,j}$，表示第$i$位以$j$个1结尾的概率，那么易得：

$$f_{i,j}= \begin{cases} 0~~~~~~~~~~~~~~~~~~~~~~i<j \\ f_{i-1,j-1}\cdot p_i~~~~~i\geq j 且 j>0\\ 1-p_i~~~~~~~~~~~~~~i\geq j 且 j=0 \\ \end{cases}$$

那么显然答案为：

$$ANS=\sum_{i=1}^n (1-p_{i+1})\sum_{j=1}^i f_{i,j}*j^k$$

考虑写出$f_{i,j}$的通项：

注意到对于一般的$f$，例如$f_{6,3}$，它可以写成：

$$f_{6,3}=f_{5,2}\cdot p_6\\ =f_{4,1}\cdot p_5 \cdot p_6 \\ =f_{3,0}\cdot p_4 \cdot p_5 \cdot p_6 \\ =(1-p_3)\cdot p_4 \cdot p_5 \cdot p_6 \\$$

能感受到其通项为：

$$f_{i,j}=(1-p_{i-j})\prod_{k=i-j+1}^i p_k ~~~~~~~~~~(i>=j)$$

利用前缀积可得：

$$f_{i,j}=(1-p_{i-j})\frac{prod_i}{prod_{i-j}}~~~~~~~~~~(i>=j)$$

那么将$ANS$转化为

$$ANS=\sum_{i=1}^{n}(1-p_{i+1})\sum_{j=1}^{i} (1-p_{i-j})\frac{prod_i}{prod_{i-j}}\cdot j^k$$

将$prod_i$提至第一个$\sum$后，可转换为卷积形式：

$$ANS=\sum_{i=1}^{n}(1-p_{i+1})\cdot prod_i\sum_{j=1}^{i} \frac{1-p_{i-j}}{prod_{i-j}}\cdot j^k \\$$

设：

$$A[i]=\sum_{i\geq0} \frac{1-p[i]}{prod[i]}x^i \\ B[i]=\sum_{i\geq1} i^kx^i \\$$

故：

$$ANS=\sum_{i=1}^{n}(1-p_{i+1})\cdot prod_i\cdot [x^i](A*B)$$

总复杂度$O(n logn)$，瓶颈在NTT和快速幂，比原dp的解法的优势是：对$k$的取值是任意的，但是需要在取模意义下（故无法通过本题的浮点版本，因为前缀积在浮点意义下太容易变成0）