常见套路?

1.一部分需要求类似于\(\sum ans(x)^k\),k不大,\(ans(x)\)贡献每次多\(1\)。

解:这种题感觉突然很常见还比较套路,在联赛出现也不是不可能/kk

直接二项式定理可以做到\(O(k^2)\)更新贡献,但是并不优秀。

考虑斯特林数展开,\(x^k=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\begin{pmatrix}x\\i\end{pmatrix}\)。

如何理解?考虑组合意义,\(x^k\)为\(x\)个集合放\(k\)个数的方案数(集合可以为空),那么可以枚举非空集,\(\begin{Bmatrix}k\\i\end{Bmatrix}\)是\(i\)个集合放\(k\)个数(集合不可以为空),盒子不一样所以乘\(i!\),\(\begin{pmatrix}x\\i\end{pmatrix}\)是从\(x\)个集合选\(i\)个非空集。

于是这个式子变为\(\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\sum\begin{pmatrix}ans(x)\\i\end{pmatrix}\)。

发现每次贡献更新只会跟\(\begin{pmatrix}ans(x)\\i\end{pmatrix}\)有关,而贡献多\(1\)后,\(\begin{pmatrix}ans(x)+1\\i\end{pmatrix}=\begin{pmatrix}ans(x)\\i\end{pmatrix} + \begin{pmatrix}ans(x)\\i-1\end{pmatrix}\),于是我们维护\(\begin{pmatrix}ans(x)\\i\end{pmatrix},0\le i\le k\),每次更新贡献可以\(O(k)\)完成。

上一篇:矩阵快速幂详解


下一篇:复旦大学2018--2019学年第二学期(18级)高等代数II期末考试第六大题解答