「loj - 6703」小 Q 的序列

link。

从 https://codeforces.com/blog/entry/76447 里面抄一个代数做法。

考虑朴素 dp：记 \(f_{i, j} = f_{i - 1, j} + (j + a_i)\times f_{i - 1, j - 1}\)，不太好做。

做变换 \(g_{i, j} = f_{i, i - j}\)，并记 \(b_i = a_i + i\)，则有 \(g_{i,j} = g_{i - 1, j - 1} + (b_i - j)\times g_{i - 1, j}\)。

其对应的 OGF 满足 \(G_i = x(G_{i - 1} - G‘_{i - 1}) + b_iG_{i - 1}\)。

根据高中数学，我们可以构造 \(H_i = G_ie^{-x}\)，则有 \(H_i = b_iH_{i-1} - xH‘_{i-1}\)。

注意算子 \(\vartheta = x\frac{d}{dx}\) 只和本位系数有关，也就是说有 \(h_{n, j} = h_{0, j}\times\prod_i(b_i - j) = \frac{(-1)^j}{j!}\times\prod_i(b_i - j)\)。

之后可以分治 fft 算出 \(B(x) = \prod_i(b_i - x)\)，然后多点求值求出 \(H_n\)。

但是在本题中我们只需要算 \(\sum_i g_{n, i}\)，是否有更好的方法？

我们知道：

其中 \(B_p = [x^p]\prod_i(b_i - x)\)，一样分治 fft 算出。

考虑将 \(j^{n - p}\) 展开成下降幂形式：

则 \(\sum_i g_{n, i} = \sum_p B_p \times \left(\sum_i(-1)^i{n - p\brace i}\right)\)。接下来只需要计算 \(s_{n-p} = \sum_i(-1)^i{n - p\brace i}\)。

继续用代数做法。设出 EGF：\(S(x) = \sum\frac{s_i}{i!}x^i\)。代入：

\[\begin{aligned} S(x) =& \sum_{i}\frac{\sum_m(-1)^m{i\brace m}}{i!}x^i \=& \sum_m(-1)^m\left(\sum_{i}\frac{{i\brace m}}{i!}x^i\right) \=& \sum_m(-1)^m\frac{(e^x-1)^m}{m!} \=& \exp(1-e^x)\\end{aligned} \]

做个多项式 exp 即可求出。这真的更优秀吗。

「loj - 6703」小 Q 的序列

原文：https://www.cnblogs.com/Tiw-Air-OAO/p/14600661.html