问题

学术版

wishapig @ 2023-04-16 14:50:03

给出 n 次多项式 F(x)

对每个 i\in [1,k]，求出 [x^n]F^i(x)

这个能不能做到 k\log n 之类的复杂度

by 水军带你飞 @ 2023-04-16 14:55:37

大概不行。这个应该可以归约到多项式复合逆。

by wishapig @ 2023-04-16 15:05:42

~~原来的问题是求~~

[x^n]\dfrac{1}{1-x}\sum_{i=1}^{k}\begin{Bmatrix} k\\ i \end{Bmatrix}(-\ln(1-x))^i

by YeahPotato @ 2023-04-16 15:08:23

给定 n,k，求 n 排列的环数的 k 次方的期望。

by 水军带你飞 @ 2023-04-16 15:55:58

@wishapig 首先不必要用斯特林数，直接枚举 i 个环，就是 \sum i^k \times [x^n] (- \ln(1 - x))^i。

现在对每个 i 求 [x^n](-\ln(1 - x))^i。-(\ln(1 - x)) 的复合逆是好求的，之后直接用拉格朗日反演就行。