杂题

题意

(x=0)，(n)次操作，有(frac{Q}{Q+1})将(x)加(1)。求(E(sumlimits_{i=1}^x i^k) imes (Q+1)^n)

做法一

令(f_{n,i})为(n)次操作后(E(x^i))
显然有：(f_{n,i}=frac{1}{1+Q}f_{n-1,i}+frac{Q}{1+Q}sumlimits_{k=0}^i {ichoose k}f_{n-1,k})
令(F_n(x)=sumlimits_{i}f_{n,i}frac{x^i}{i!},G(x)=frac{1}{1+Q}+sumlimits_{i}frac{x^i}{i!})，有(F_n(x)=F_{n-1}(x)G(x))
然后就可以快速幂了
(sumlimits_{i=1}^x i^k)，可以快速插值出(k+1)次系数，因为期望是线性的，所以带入就好了

做法二

这个没什么意思
(egin{aligned} Ans&=sumlimits_{i=0}^n {nchoose i}Q^isumlimits_{j=1}^i j^k\ &=sumlimits_{i=0}^n {nchoose i}Q^isumlimits_{j=1}^i sumlimits_{t=0}^k S_{k,t}{jchoose t}t!\ &=sumlimits_{t=0}^k t!S_{k,t}sumlimits_{i=t}^n {nchoose i}Q^isumlimits_{j=0}^i {jchoose t}\ &=sumlimits_{t=0}^k t!S_{k,t}sumlimits_{i=t}^n {nchoose i}Q^i{i+1choose t+1}\ &=sumlimits_{t=0}^k frac{S_{k,t}}{t+1}Q^t n^{underline t}sumlimits_{i=0}^{n-t}{n-tchoose i}(i+t+1)Q^i\ &=sumlimits_{t=0}^k frac{S_{k,t}}{t+1}Q^t n^{underline t}((t+1)(Q+1)^{n-t}+(n-t)Q(Q+1)^{n-t-1})\ end{aligned})