题解 CF1677F【Tokitsukaze and Gems】

又是我毛不会的数数题。 --- 单独考虑每个位置的贡献，容易转化为答案就是 $$\sum\limits_{i=1}^ncoef_i\sum\limits_{j=0}^{a_{i}}p^j j^k$$ $$coef_i=\sum\limits_{l=1}^i\sum\limits_{r=i}^n\sum\limits_{j=l}^r\prod_{t\in[l,r],t\neq i}(a_t+[t\neq j])$$ 求 $coef_i$ 可以发现 $i$ 左侧和右侧独立，所以可以 dp，最后两边合并一下即可。 设 $m=a_i$，令 $f(k)=\sum_{i=0}^mp^i i^k$。 则 $\sum_{i=0}^mp^{i+1} (i+1)^k=f(k)+p^{m+1}(m+1)^k-0^k$ 左边展开然后移项可得： $$\left(p\sum_{j=0}^kf(j)\binom{k}{j}\right)-f(k)=p^{m+1}(m+1)^k-0^k$$ 设 $F(x)=\sum_{i} f(i)\frac{x^i}{i!}$，$G(x)=\sum_{i} p\frac{x^i}{i!}-1=p\mathrm{e}^x-1$ 那么就变成了： $$F(x)=\frac{1}{G(x)}\left(\left(\sum\limits_{t}p^{m+1}(m+1)^t\frac{x^t}{t!}\right)-1\right)$$ $$\begin{aligned}f(k)=k![x^k]F(x)&=k!\left(-[x^k]\frac{1}{G(x)}+\sum\limits_{j=0}^k[x^{k-j}]\frac{1}{G(x)}\times \left(\frac{p^{m+1}(m+1)^j}{j!}\right)\right) \\ &=k!\left(-[x^k]\frac{1}{G(x)}+p^{m+1}\sum\limits_{j=0}^k[x^{k-j}]\frac{(m+1)^j}{G(x)j!}\right) \end{aligned}$$ 右边可以看成关于 $(m+1)$ 的 $k$ 次多项式，所以多项式多点求值即可。 时间复杂度是 $\mathcal{O}(k\log k+n\log^2n)$。 [**code**](https://codeforces.com/contest/1677/submission/156568533)